CPC '21 Contest 1 P1 - AQT and Fractions

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

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?


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

1 3
2 5
3 9
1 4

Sample Output 1


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.


There are no comments at the moment.