Euler's Totient Function and GCD Utility

In this problem, you are required to compute Euler's Totient Function, denoted by \( \varphi(n) \). The totient function \( \varphi(n) \) is defined as the number of positive integers up to \( n \) that are coprime to \( n \). Two numbers are coprime if their greatest common divisor (gcd) is 1.

You will implement two functions:

• gcd(a, b): Computes the greatest common divisor of a and b.
• euler_totient(n): Uses the gcd function to compute \( \varphi(n) \) by counting the numbers that are coprime with n.

Note: You should read the input from standard input (stdin) and write the output to standard output (stdout).

For example, if the input is:

3
1
2
3

Then the output should be:

1
1
2

inputFormat

The input begins with a single integer T (\( T \ge 1 \)), representing the number of test cases. Each of the following T lines contains a single integer \( n \) (\( n \ge 1 \)).

Each test case should be processed independently.

outputFormat

For each test case, output a single line containing the value of Euler's Totient Function \( \varphi(n) \).

## sample

3
1
2
3

1
1
2

</p>