I Am Good

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.