Euler Totient Function Calculation

Determine the count of numbers between 1 and a given integer 'N' (inclusive) that are coprime to 'N'.

Input:

T, number of test cases
N, the integer for each test case

Output:

The count of integers coprime to N for each test case.

Example:

Input:

1
9

Output:

6

Explanation:

For N = 9, the integers 1, 2, 4, 5, 7, and 8 are coprime to 9.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 10 ^ 9
• Time Limit: 1 sec

Note:

Two numbers are coprime if their greatest common divisor (GCD) is 1. Additionally, 1 is coprime to any number.