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:
| • 100 | a = 100 | b = 1 | (terminates) |
| • -1.875 | a = -15 | b = 8 | (terminates) |
| • 2.16 | a = 13 | b = 6 | r = 6 |
| • 7.27 | a = 80 | b = 11 | r = 27 |
| • 0.285714 | a = 2 | b = 7 | r = 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.
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.
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.
|