Migrated from Lutece 668 Kalindrome

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A palindromic number is a number that remains the same when its digits are reversed. Like 16461, for example, it is "symmetrical".

Now Krolia want to know the $K_{th}$-largest palindromic number which is smaller than $n$.

Input

There is only one integer $T$($T\leq 100$) in the first line, indicating the number of test cases.

Every test cases contains two integers $n$($0\leq n\leq 10^{100}$), $k$($1\leq k\leq 100$).

Output

For every test cases, just output a the $k_{th}$-largest palindromic number in one line. If this number doesn't exist, output $-1$.

Samples

5
10 1
1 1
1 2
100 1
112 2

9
0
-1
99
101

Resources

KroliaFansClub