H. Strength
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

People often use approximate methods to express numerical values in everyday conversations. Whether discussing time, money, or other numbers, people tend to round off to make communication simpler and easier. For example, if you and your friends dine at a restaurant with a bill of $$$98$$$ yuan, many would say, "The bill is a hundred yuan," instead of using the exact number.

If we take a more aggressive approach and round multiple times, the final result can become absurd. For instance, you could round $$$145$$$ up to $$$200$$$, because $$$145$$$ can be rounded to $$$150$$$, which can then be rounded to $$$200$$$; when someone says $$$2000$$$, it could actually have been $$$2001$$$, $$$1999$$$, $$$1888$$$, or even $$$11451$$$ before rounding.

Given a number $$$x$$$, calculate the uncertainty of $$$x$$$ within the range $$$[0,z]$$$, which is the count of numbers within the range $$$[0,z]$$$ that can be $$$x$$$ after aggressive rounding. Here, aggressive rounding is defined as performing the following rounding operation arbitrarily (possibly zero) times:

  • Let the decimal representation of $$$x$$$ be $$$\overline{x_k x_{k - 1} \dots x_1}$$$, and choose an index $$$i \in \{1, 2, \dots, k\}$$$.
  • If $$$x_i \lt 5$$$, subtract $$$x_i \cdot 10^{i-1}$$$ from $$$x$$$;
  • otherwise, add $$$(10 - x_i) \cdot 10^{i-1}$$$ to $$$x$$$.
Input

The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The input contains two integers in a line: $$$x$$$ and $$$z$$$ ($$$0 \le x,z \le 10^{18}$$$). Refer to above for their meanings.

Output

Each line contains a single number, representing the uncertainty of $$$x$$$ in the range $$$[0,z]$$$.

Example
Input
5
0 2147483646
10 100
671232353 1232363
123001006660996 3122507962333010
100019990010301090 44519984489341188
Output
2147483647
55
0
1919810
114514
Note

In the second test case, $$$10i + j$$$ ($$$i=0,1,\cdots,9$$$, $$$j=5,6,7,8,9$$$) and $$$10,11,12,13,14$$$ can be aggressively rounded to $$$10$$$. Thus, the answer is $$$55$$$.