# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Easy Factorial?

By sagarthecoder · Limits 1s, 512 MB

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

InputOutput
```2
4
5
```
```Case 1: 2
Case 2: 1
```

### Statistics

100% Solution Ratio

Nasim_Ahmed71Earliest, 1M ago

moursalinmeFastest, 0.1s

moursalinmeLightest, 6.8 MB

purpleShortest, 542B

### Submit 