Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4085
Little Sub and Mr.Potato's Math Problem

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Little Sub loves math very much. He enjoys counting numbers.

One day, Mr.Potato gives him an interesting math problem. Please help Little Sub solve this problem.

Let's sort the integers $1, 2, \dots, N$ according to alphabetical order. For example, when $N=11$, the order should be: $1,10,11,2,3,4,5,6,7,8,9$.

We define $Q(N, K)$ as the position of number $K$ in the sorted $N$ numbers. For example, $Q(11, 2)=4$.

Given $K$ and $M$, please find the smallest $N$ such that $Q(N, K) = M$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$), indicating the number of test cases. For each test case:

The first and only line contains two integers $K$ and $M$ ($1 \le K \le 10^8$, $1 \le M \le 10^8$).

Output

For each test case, please output the answer in one line. If there is no such $N$, please output "0" (without quotes).

Sample Input

2
2 4
10000001 100000000

Sample Output

11
1000000088888880

Author: ZHANG, Zhihuan
Source: ZOJ Monthly, January 2019
Submit    Status