B. Interesting Connection
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For two positive integers $$$x,y$$$,define $$$con(x,y)$$$ as the number obtained by connecting the decimal representation of $$$x$$$ with $$$y$$$, where $$$x$$$ is on the left and $$$y$$$ is on the right.For example $$$con(20,23)=2023,con(2,33)=233$$$.

You're given two integers $$$n,k$$$.You can choose an array $$$a$$$ of positive integers of size $$$n$$$,which satisfies $$$\Sigma_{i=1}^{n}a_i=k$$$.

Define the score as the number of prime numbers among all $$$con(a_i, a_j)(1\leq i,j\leq n)$$$.Find the minimum score you can get.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le k \le 10^9$$$).

Output

For each test case, output a single integer — the minimum score you can get.

Example
Input
6
2 3
2 5
3 3
3 7
3 17
1 1000000000
Output
1
1
9
2
0
0
Note

Test Case $$$1$$$:

One of the optimal array $$$a$$$ is $$$[1,2]$$$.

For this array,$$$con(a_1,a_1)=11,con(a_1,a_2)=12,con(a_2,a_1)=21,con(a_2,a_2)=22$$$.

There's only one prime.It can be proven that $$$1$$$ reaches the minimum.

Test Case $$$2$$$:

One of the optimal array $$$a$$$ is $$$[2,3]$$$.

For this array,$$$con(a_1,a_1)=22,con(a_1,a_2)=23,con(a_2,a_1)=32,con(a_2,a_2)=33$$$.

There's only one prime.It can be proven that $$$1$$$ reaches the minimum.

Test Case $$$3$$$:

The only array $$$a$$$ you can choose is $$$[1,1,1]$$$.

For this array,$$$con(a_i,a_j)=11$$$ for all $$$1 \le i,j \le n$$$.

There're $$$9$$$ primes.It can be proven that $$$9$$$ reaches the minimum.