405089: GYM101778 J Gin Passwords

Gin is a high-ranking member of the Black Organization. During the last period, Gin made many thefts and collected a huge wealth. Now, Gin wants to hide his wealth in a secret safe, and he must choose a very strong password for it.

Every time Gin wants to pick a new password he chooses two numbers l and r, then the new password will be the largest number x (l ≤ x ≤ r) that its decimal representation can be divided into two non-zero halves (of the same length) and the two halves are relatively prime. Two numbers are relatively prime if the only positive integer (factor) that divides both of them is 1.

In case a number x have odd number of digits (2r + 1), the first half will have the first r + 1 digits in the decimal representation of x (from the left), and the second half will contain the remaining r digits in the decimal representation of x.

Can you help Gin in choosing his new passwords?

The first line contains an integer T (1 ≤ T ≤ 10⁵), in which T is the number of test cases.

Each test case contains two numbers l and r (1 ≤ l ≤ r ≤ 10¹⁸), as described in the statement.

For each test case, print the largest number x (l ≤ x ≤ r) that its decimal representation can be divided into two non-zero halves and the two halves are relatively prime. If a number x does not exist in the given range, print  - 1.

2
21 25
110 186

25
185

In the first test case, there are 3 numbers in the range [21, 25] that can be chosen as a password. These numbers are 21, 23, and 25. Gin will choose the largest one of them as a password, which is 25.