The Phi function (sample, not for credit)

The quantity φ(n) is defined to be the number of integers between 1 and n (inclusive) that are relatively prime to n. Your task is to compute this quantity for various values of n.

Input

The first line gives the number of test cases, T. T test cases follow. Each test case is a single line containing one positive integer, n.

Output

For each test case, output one line containg "Case #x: y", where x is the case number (starting from 1) and y is the value φ(n).

Limits

Sample

Input and output files

Sample solutions

Below are links to four different solutions to this problem. These show two different algorithms: a naive implementation which explicitly checks every number from 1 to n to see if it is coprime (using the Euclidean algorithm), and an implementation which removes prime factors one by one and uses the multiplicative property of the phi function. Each algorithm is implemented in C++ and in Python.

The naive algorithm is fast enough to complete the small input in a couple minutes, but would be hopeless for the large input. The faster algorithm can complete the large input in about ten minutes. There are various optimizations that could make it faster still, which I encourage you to search for.