Problem Description

uuku is learning digit DP.

But one day, he found that among the nine digits $1,2,\ldots,9$, the digit $x$ disappeared. That is, all numbers that contain the digit $x$ disappeared.

This made him very nervous, because it has a big impact on counting how many numbers there are.

Now, he wants you to help him find the rank of the number $n$ among the natural numbers that did not disappear, when ordered from small to large.

Input Format

This problem has multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 10^5$), which indicates the number of test cases.

For each test case:

There is one line with two integers $n, x$ ($0 \leq n \leq 10^{18}, 1 \leq x \leq 9$), separated by a space, with meanings as described in the statement.

The testdata guarantees that $n$ does not contain the digit $x$.

Output Format

For each test case, output one integer per line, which is the rank of $n$.

5
9 4
99 7
12345678 9
9475632111234123 8
998244353114514 7

9
81
6053445
1758041005111510
205404686678741

Hint

For the first test case in the sample, the sequence of natural numbers becomes $0,1,2,3,5,6,7,8,9$, where $9$ is the $9$-th.

Translated by ChatGPT 5