11790번 - Primorial vs LCM 다국어

문제

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.

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 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.

제한

힌트