In the math class, the evil teacher gave you one unprecedented problem!
Here f(n) is the n-th fibonacci number (n >= 0)! Where f(0) = f(1) = 1 and for any n > 1, f(n) = f(n - 1) + f(n - 2). For example, f(2) = 2, f(3) = 3, f(4) = 5 ...
The teacher used to let you calculate f(n) mod p where n <= 10^18 and p <= 10^9, however , as an ACMER, you may just kill it in seconds! The evil teacher is mad about this. Now he let you find the smallest integer m (m > 0) such that for ANY non-negative integer n ,f(n) = f(n + m) (mod p) . For example, if p = 2, then we could find know m = 3 , f(0) = f(3) = 1(mod 2), f(1) = f(4) (mod 2) ....
Now the evil teacher will only give you one integer p( p <= 2* 10^9), will you tell him the smallest m you can find ?
Input
The first line is one integer T indicates the number of the test cases. (T <=20)
Then for every case, only one integer P . (1 <= P <= 2 * 10^9, the max prime factor for P is no larger than 10^6)
Output
Output one line.
First output “Case #idx: ”, here idx is the case number count from 1.Then output the smallest m you can find. You can assume that the m is always smaller than 2^64 .
SampleInput
5
11
19
61
17
67890
SampleOutput
Case #1: 10
Case #2: 18
Case #3: 60
Case #4: 36
Case #5: 4440