Given N (2<=N<=10¹⁴), what is the quotient of LCM(1,2,3,....,N) divided by multiple of all primes up to N. As the result might be too big, output it's modulo by 1000000007.</p>

For example, when N=5, the result is LCM(1,2,3,4,5)/(235)=60/30=2.

Note that LCM stands for Lowest or Least Common Multiple. 

입력 형식

The first line of the input is T(T ≤ 50000), then T test cases follows in next T lines. Each line contains an integer N (2 ≤ N ≤ 100000000000000 or 10¹⁴). The meaning of N is given in the problem statement. 

출력 형식

For each test case print a line in “Case x: S” format where x is case number and S is the quotient modulo by 1000000007. 

예제 입력

10
2
3
4
5
6
7
8
9
10
1000

예제 출력

Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 2
Case 5: 2
Case 6: 2
Case 7: 4
Case 8: 12
Case 9: 12
Case 10: 744593350