Hanamichi is taking part in a programming contest, and he is assigned to solve a special problem as follow: Given a range [l, r] (including l and r), find out how many numbers in this range have the property: the sum of its odd digits is smaller than the sum of its even digits and the difference is 3.
A integer X can be represented in decimal as:
\(X = A_n\times10^n + A_{n-1}\times10^{n-1} + \ldots + A_2\times10^2 + A_1\times10^1 + A_0\)
The odd dights are \(A_1, A_3, A_5 \ldots\) and \(A_0, A_2, A_4 \ldots\) are even digits.
Hanamichi comes up with a solution, He notices that:
\(10^{2k+1}\) mod 11 = -1 (or 10), \(10^{2k}\) mod 11 = 1,
So X mod 11
= \((A_n\times10^n + A_{n-1}\times10^{n-1} + \ldots + A_2\times10^2 + A_1\times10^1 + A_0) \mod 11\)
= \(A_n\times(-1)^n + A_{n-1}\times(-1)^{n-1} + \ldots + A_2 - A_1 + A_0\)
= sum_of_even_digits ¨C sum_of_odd_digits
So he claimed that the answer is the number of numbers X in the range which satisfy the function: X mod 11 = 3. He calculate the answer in this way :
Answer = (r + 8) / 11 ¨C (l ¨C 1 + 8) / 11.
Rukaw heard of Hanamichi¡¯s solution from you and he proved there is something wrong with Hanamichi¡¯s solution. So he decided to change the test data so that Hanamichi¡¯s solution can not pass any single test. And he asks you to do that for him.
Input
You are given a integer T (1 ¡Ü T ¡Ü 100), which tells how many single tests the final test data has. And for the following T lines, each line contains two integers l and r, which are the original test data. (1 ¡Ü l ¡Ü r ¡Ü \(10^{18}\))
Output
You are only allowed to change the value of r to a integer R which is not greater than the original r (and R ¡İ l should be satisfied) and make Hanamichi¡¯s solution fails this test data. If you can do that, output a single number each line, which is the smallest R you find. If not, just output -1 instead.
