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 #69: Totient maximum

# Project Euler #69: Totient maximum

# Project Euler #69: Totient maximum

_{This problem is a programming version of Problem 69 from projecteuler.net}

Euler's Totient function, [sometimes called the phi function], is used to determine the number of numbers less than which are relatively prime to . For example, as and , are all less than nine and relatively prime to nine, .

It can be seen that produces a maximum for . Find the value of for which is maximum. In case of multiple answers, print the minimum.

**Input Format**

First line contains , denoting number of test cases. lines follow

Each line contains

**Constraints**

**Output Format**

Print the answer corresponding to each testcase on a new line.

**Sample Input**

```
2
3
10
```

**Sample Output**

```
2
6
```