Description

One day, you are playing a game called “Simple Number” with CKL.

The rules of the game is following:

At first, the judge decides a positive integer R to be the range.
Then, CKL will start the game. The two players try to find a special integer N in turns.
The special integer N is a positive integer less than R.
N is co-prime with R. (that is, gcd⁡(N, R) = 1)
The player who cannot find the new N will lose the game.

For example, if the judge decides R is 8, then one of the game’s situations will be:

• Turn 1: CKL chose 1.
• Turn 2: You chose 7.
• Turn 3: CKL chose 5.
• Turn 4: You chose 3.
• CKL loses!!!!!!

But you are a lazy person. You don’t want to play too many turns. Just want to know how many turns will be played under the range R. Please write a program to solve it.

Input

The first line of the input is an integer Z (Z ≤ 10⁵), which means the number of test cases.
For each test case, one line contains one positive integer R (R ≤ 10⁹).

Output

For each test case, output the test case number and the turns of the game under the range R.

Sample Input  Download

Sample Output  Download

Tags

Discuss