This problem is a programming version of Problem 72 from projecteuler.net
Consider the fraction, , where and are positive integers. If and , it is called a reduced proper fraction.
If we list the set of reduced proper fractions for in ascending order of size, we get:
It can be seen that there are elements in this set.
How many elements would be contained in the set of reduced proper fractions for ?
Input Format
First line contains , number of test cases. lines follow
Each line contains 1 integer
Constraints
Output Format
Print the result corresponding to each testcase on a new line.
Sample Input
2
8
5
Sample Output
21
9