시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 99 24 22 24.719%

문제

Given N (2<=N<=1014), 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.

For example, when N=5, the result is LCM(1,2,3,4,5)/(2*3*5)=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 1014). 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

힌트