405082: GYM101778 C Professor Agasa Lab

C. Professor Agasa Labtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Professor Agasa always tries to help Conan solve the crimes and he has invented all Conan's special gadgets.

Currently, Professor Agasa is solving a complex murder case, so he is performing a series of tests in his laboratory. After two months of searching, Professor Agasa figured that all the evidence he needs to solve the case can be found in a safe inside one of the suspect's house. Professor Agasa is so close to open the safe, he only needs to solve one more puzzle and all the secrets inside the safe will be for him. The final puzzle is as follows:

If you have the following equation

If you know the values of y, a, b, and m, then you can calculate the value of x as follows: Where a^- 1 is the multiplicative inverse of a number a, such that a^- 1 exists only if gcd(a, m) ≡ 1.

You are given m, count how many different pairs (a, b) (1 ≤ a, b < m) exist, such that you can use them to calculate y and x under the given modules m.

Professor Agasa is so tired of solving puzzles all the day in order to open the safe. Can you help him by solving the last puzzle?

Input

The first line of the input contains an integer T (1 ≤ T ≤ 10⁵), in which T is the number of test cases.

Then T lines follow, each line contains an integer m (1 ≤ m ≤ 10⁶), in which m is the described modulus in the problem statement.

Output

For each test case, print a single line containing how many different pairs (a, b) (1 ≤ a, b < m) exist, such that Professor Agasa can use them to calculate y and x under the given modules m.

ExampleInput

2
6
10

Output

10
36

Note

In the first test case, there are 10 different pairs that satisfy the problem conditions, which are: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (5, 1), (5, 2), (5, 3), (5, 4), and (5, 5)