We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #72: Counting fractions

# Project Euler #72: Counting fractions

# 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
```