I Am Good

Limits 2s, 512 MB

I am trying to become a good guy, because it doesn't take money to become good. So here's a short and simple problem statement because I am a good guy! 🙂

Given two integers $X$ and $P$ , find the minimum positive value of $K$ such that $f(X, K)$ is divisible by $P$ .

$f(X, K)$ is defined as the $K$ -times concatenation of the integer $X$ (without leading zeroes).

For example,

$f(123, 3) = 123123123$
$f(54, 4) = 54545454$
$f(123, 2) = 123123$
$f(7, 5) = 77777$

Input

Input will start an integer $T$ ( $1 \le T \le 10$ ) denoting the number of test cases.

In each test case, two space separated integers $X$ ( $1 \le X \le 10^4$ ) and $P$ ( $1 \le P \le 10^{10}$ ) will be given.

Output

For each test case, print the minimum positive value of $K$ in a single separate line.

If no such $K$ exists, print -1.

Sample

Input	Output
2 123 9 123 10	3 -1
In the first test case, $f(123, 3) = 123123123$ is divisible by 9 while 123123 and 123 are not divisible by 9. Thus 3 is the minimum possible value of $K$ for this test case. In the second test case, $f(123, K)$ can never be divisible by 10 no matter what $K$ is.

Input

Output

2
123 9
123 10

3
-1

In the first test case, $f(123, 3) = 123123123$ is divisible by 9 while 123123 and 123 are not divisible by 9. Thus 3 is the minimum possible value of $K$ for this test case.

In the second test case, $f(123, K)$ can never be divisible by 10 no matter what $K$ is.