From Zero To Y
Description
You are given two positive (greater than zero) integers $x$ and $y$. There is a variable $k$ initially set to $0$.
You can perform the following two types of operations:
- add $1$ to $k$ (i. e. assign $k := k + 1$);
- add $x \cdot 10^{p}$ to $k$ for some non-negative $p$ (i. e. assign $k := k + x \cdot 10^{p}$ for some $p \ge 0$).
Find the minimum number of operations described above to set the value of $k$ to $y$.
The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.
Each test case consists of one line containing two integer $x$ and $y$ ($1 \le x, y \le 10^9$).
For each test case, print one integer — the minimum number of operations to set the value of $k$ to $y$.
Input
The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.
Each test case consists of one line containing two integer $x$ and $y$ ($1 \le x, y \le 10^9$).
Output
For each test case, print one integer — the minimum number of operations to set the value of $k$ to $y$.
Samples
3
2 7
3 42
25 1337
4
5
20
Note
In the first test case you can use the following sequence of operations:
- add $1$;
- add $2 \cdot 10^0 = 2$;
- add $2 \cdot 10^0 = 2$;
- add $2 \cdot 10^0 = 2$.
In the second test case you can use the following sequence of operations:
- add $3 \cdot 10^1 = 30$;
- add $3 \cdot 10^0 = 3$;
- add $3 \cdot 10^0 = 3$;
- add $3 \cdot 10^0 = 3$;
- add $3 \cdot 10^0 = 3$.