AQT is studying fractions and he has encountered $T$ problems. In each problem, AQT is given a fraction with a numerator $A$ and a denominator $B$ $(A<B)$. AQT wants to know after converting the fraction to a decimal and removing all terminating zeroes, how many digits there are to the right of the decimal. Can you help AQT answer all $T$ problems?

Constraints

For all subtasks:

$1\le T\le {10}^3$

$1\le A<B\le {10}^{18}$

Subtask 1 [10%]

$T=1$

$1\le A<B\le 5$

Subtask 2 [10%]

$B$ is a multiple of $10$.

Subtask 3 [30%]

$1\le A<B\le {10}^9$

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains $T$, the number of problems you need to help AQT solve.

The next $T$ lines contain $A$ and $B$, the numerator and the denominator of the fraction, respectively.

Output Specification

For each problem, output the answer to the problem if the answer is finite, or -1 if the answer is infinite.

Sample Input 1

4
1 3
2 5
3 9
1 4

Sample Output 1

-1
1
-1
2

Explanation for Sample 1

For the first test case, $\frac{1}{3}=0.\bar{3}$.

For the second test case, $\frac{2}{5}=0.4$.

For the third test case, $\frac{3}{9}=0.\bar{3}$.

For the fourth test case, $\frac{1}{4}=0.25$.