Easy Factorial?

It is time to show your performance on number theory. Why so late? Come to the point.
You are given an integer number X (1 ≤ X ≤ 106). You need to calculate
R! where R is the number of integers k in the range 1 ≤ k ≤ X for which the greatest common divisor gcd(X, k) is not equal to 1.
As the result can be very large, you should print the value modulo 109 + 7 (the remainder when divided by 109 + 7).

Input

The first line of the input contains one integer t (1≤t≤100000) — the number of test cases.
Each of next t lines contain one integer X(1≤X≤1000000).

Output

For every test case, output one integer in a separate line in the format Case A: B where A is the number of the test case starting from 1 and B is the desired output.

Sample

Input	Output
2 4 5	Case 1: 2 Case 2: 1