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
First line contains , number of test cases. lines follow
Each line contains 1 integer
Print the result corresponding to each testcase on a new line.