405244: GYM101856 H Half Nice Years

Salah is really optimistic about the qualification of the Egyptian football team for the world cup 2018. He was thinking deeply about why it didn't happen often that the Egyptian team qualified to the world cup, so he decided to call 2018 a half-nice year. He comes up with the hypothesis that the Egyptian team will always qualify to the world cup only if it is held in a half-nice year. In order to test his hypothesis we need to find the largest half-nice number in a given range [A, B]. He says a given number X is half-nice if its decimal representation can be divided into two non-zero halves(of the same length) and the two halves have a non-trivial common divisor (there's a number d > 1 that divides both parts). In case a number X have odd number of digits (2r + 1), then the first half will have the first r digits in the decimal representation of X (from the left), and the second half will contain the remaining r + 1 digits in the decimal representation of X.

The first line of the input consists of a single integer 1 ≤ T ≤ 10⁵ the number of test cases. Each test case consists of one line containing 2 space separated integers A, B, where 10 ≤ A ≤ B ≤ 10¹³.

For each test case output a single line displaying the case number, then followed by either a single integer X, which is the largest half-nice number in the range [A, B] or 'impossible' if there are no such numbers.

3
20 21
10 2019
4000 4005

Case 1: impossible
Case 2: 2018
Case 3: 4005

• The number 20122 is a half-nice number (hopefully the Egyptian team qualifies that year), because it's two halves 20 and 122 have a non-trivial common divisor which is 2.
• The number 2000 is not a half-nice number because the second half is zero.
• In the third, test case 4005 is half-nice because 40 and 5 share the non-trivial common divisor 5. It is allowed for the second half to have trailing zeros.