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.\overline{3}~.

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

For the third test case, ~\frac{3}{9} = 0.\overline{3}~.

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