Problem Description

Acesrc is a famous mathematician at Nanjing University second to none. Playing with interesting numbers is his favorite. Today, he finds a manuscript when cleaning his room, which reads

... Let $f(d, n)$ denote the number of occurrences of digit $d$ in decimal representations of integers $1, 2, 3, \cdots, n$. The function has some fantastic properties ...

... Obviously, there exist some nonnegative integers $k$, such that $f(d, k) = k$, and I decide to call them $d$-good numbers ...

... I have found all $d$-good numbers not exceeding $10^{1000}$, but the paper is too small to write all these numbers ...

Acesrc quickly recollects all $d$-good numbers he found, and he tells Redsun a question about $d$-good numbers: what is the maximum $d$-good number no greater than $x$? However, Redsun is not good at mathematics, so he wants you to help him solve this problem.

Input

The first line of input consists of a single integer $q$ $(1 \leq q \leq 1500)$, denoting the number of test cases. Each test case is a single line of two integers $d$ $(1 \leq d \leq 9)$ and $x$ $(0 \leq x \leq 10^{18})$.

Output

For each test case, print the answer as a single integer in one line. Note that $0$ is trivially a $d$-good number for arbitrary $d$.

3
1 1
1 199999
3 0

1
199990
0