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

Discussion

Statistics


100% Solution Ratio

Nasim_Ahmed71Earliest, 1M ago

moursalinmeFastest, 0.1s

moursalinmeLightest, 6.8 MB

purpleShortest, 542B

Submit

Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC