The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 6:

- Kotlin 1.4.0

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. From Zero To Y

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

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$$$.

Example

Input

3 2 7 3 42 25 1337

Output

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$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/12/2021 08:50:09 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|