G. Disappearing Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

uuku is learning digital dynamic programming.

But one day, he found that the $$$x$$$ in the nine digits of $$$1,2,\ldots,9$$$ had disappeared, which means that all numbers containing the digit $$$x$$$ had disappeared.

This made him very panicked because it had a significant impact on the number of statistics.

Now, he hopes you can help him find out where the number $$$n$$$ ranks among the natural numbers that have not disappeared in this situation.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), indicating the number of test cases.

For each test case:

The first line contains two positive integers $$$n$$$ and $$$x$$$ ($$$0 \leq n \leq 10^{18}$$$, $$$1 \leq x \leq 9$$$).

It's guaranteed that $$$n$$$ doesn't include $$$x$$$.

Output

For each test case, output a number indicating the ranking of $$$n$$$.

Example
Input
5
9 4
99 7
12345678 9
9475632111234123 8
998244353114514 7
Output
9
81
6053445
1758041005111510
205404686678741
Note

For the first example, the natural sequence becomes $$$0,1,2,3,5,6,7,8,9$$$, where the number $$$9$$$ is the $$$9$$$ th.