ACM-ICPC Indonesia National Contest 2016

Problem J

Rational Number

Time Limit: 1 second

A rational number is any real number which can be written as the fraction a/b of two whole numbers (integers) a and b. One property of a rational number is it either terminates after a finite number of digits or it has a repeating decimal digits (r). Example of rational numbers are:

•  100a = 100b = 1(terminates)
•  -1.875a = -15b = 8(terminates)
•  2.16a = 13b = 6r = 6
•  7.27a = 80b = 11r = 27
•  0.285714a = 2b = 7r = 285714

The overlined numbers in above examples represent the repeating decimal digits, e.g., 2.16 means the number is 2.166666..., while 0.285714 means the number is 0.285714285714285714285714...; 100 and -1.875 do not have repeating decimal digits as they terminate.

In this problem, you are challenged to find the length of the repeating decimal digits of a rational number. In the examples above, when a = 13 and b = 6, then the length of its repeating decimal digits is 1; while, when a = 2 and b = 7, the length of its repeating decimal digits is 6.


Input

The first line of input contains an integer T (T ≤ 100) denoting the number of cases. Each case contains two integers in a line: a b (-1,000,000,000 ≤ a, b ≤ 1,000,000,000; b ≠ 0) which represent the numerator and denominator of the rational number, respectively.

Output

For each case, output in a line "Case #X:" where X is the case number, starts from 1, and Y is the length of the repeating decimal digits for that particular case.


Sample InputOutput for Sample Input
5
100 1
-15 8
13 6
80 11
2 7
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 2
Case #5: 6