Many products in the market are priced like 999, 4999, or 8999. There is no essential difference between these and 1000, 5000, or 9000, but psychologically they feel much cheaper, which is why this is a common pricing strategy used by merchants. However, you find this kind of pricing quite absurd. Therefore, you calculate the "absurdity" of a price $p$ (where $p$ is a positive integer) as follows:

1. First, treat $p$ as a string of digits (without leading zeros).
2. Then, if the last character of $p$ is '0', remove it. Repeat this process until the last character of $p$ is not '0'.
3. Let $a$ be the length of $p$ at this point. If the last digit of $p$ is '5', the absurdity is $2 \times a - 1$; otherwise, it is $2 \times a$.

For example, the absurdity of 850 is 3, while 880 is 4, and 9999 is 8.

Now, you want to sell an item, and you can accept any price in the range $[L, R]$. You want to choose a price with the minimum absurdity.

Input

The first line of the input contains a positive integer $T$, representing the number of test cases. Each test case occupies a single line and contains two space-separated positive integers $L$ and $R$, representing the price range.

Output

For each test case, output the result on a single line. If there are multiple prices with the same minimum absurdity, output the smallest one.

Constraints

• For 20% of the data, $L, R \le 2000$.
• For 100% of the data, $T \le 100$, $1 \le L \le R \le 10^9$.

Examples

Input 1

3
998 1002
998 2002
4000 6000

Output 1

1000
1000
5000