Project Euler #72: Counting fractions

_{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