codeforces#P1488A. From Zero To Y

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:

  1. add $1$;
  2. add $2 \cdot 10^0 = 2$;
  3. add $2 \cdot 10^0 = 2$;
  4. add $2 \cdot 10^0 = 2$.
$1 + 2 + 2 + 2 = 7$.

In the second test case you can use the following sequence of operations:

  1. add $3 \cdot 10^1 = 30$;
  2. add $3 \cdot 10^0 = 3$;
  3. add $3 \cdot 10^0 = 3$;
  4. add $3 \cdot 10^0 = 3$;
  5. add $3 \cdot 10^0 = 3$.
$30 + 3 + 3 + 3 + 3 = 42$.