// Arup Guha
// 2/23/2014
// Solution to COT 3100 Program 3: Calculating Euler Phi Function

import java.util.*;

public class phi {

	final static int MAXPRIME = 1000000;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Precompute prime list.
		int[] primes = sieve(MAXPRIME);

		// Go through each case.
		for (int loop=0; loop<numCases; loop++) {
			long n = stdin.nextLong();
			ArrayList<factor> factorList = getPrimeFact(n, primes);
			System.out.println(phi(factorList));
		}
	}

	// Runs Prime Sieve and returns an array of all primes upto limit,
	// stored in order.
	public static int[] sieve(int limit) {

		// Set up sieve.
		boolean[] isPrime = new boolean[limit+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;

		// Run regular sieve.
		for (int i=2; i<Math.sqrt(isPrime.length)+.01; i++)
			for (int j=2*i; j<isPrime.length; j+=i)
				isPrime[j] = false;

		// Count primes.
		int numPrimes = 0;
		for (int i=0; i<isPrime.length; i++)
			if (isPrime[i])
				numPrimes++;

		// Copy over primes.
		int[] primes = new int[numPrimes];
		int index = 0;
		for (int i=0; i<isPrime.length; i++)
			if (isPrime[i])
				primes[index++] = i;

		return primes;
	}

	// Returns the prime factorization of n, where n <= 10^12, using primes,
	// which stores all primes to 10^6.
	public static ArrayList<factor> getPrimeFact(long n, int[] primes) {

		ArrayList<factor> list = new ArrayList<factor>();

		// Go through each prime.
		for (int i=0; i<primes.length; i++) {

			// See if this one divides in.
			int exp = 0;
			while (n%primes[i] == 0) {
				n /= primes[i];
				exp++;
			}

			// Add if necessary.
			if (exp > 0) list.add(new factor(primes[i], exp));

			// We're done!
			if (n == 1) break;
		}

		// Last item left is prime!
		if (n > 1) list.add(new factor(n, 1));

		return list;
	}

	// Calculates phi of n making use of its multiplicative property.
	public static long phi(ArrayList<factor> list) {
		long ans = 1;
		for (int i=0; i<list.size(); i++)
			ans *= list.get(i).phi();
		return ans;
	}
}

class factor {

	// Store running value to make phi calculation efficient.
	private long prime;
	private int exp;
	private long value;

	// Constructor for multiple copies of prime.
	public factor(long p, int e) {
		prime = p;
		exp = e;
		value = 1;
		for (int i=0; i<exp; i++)
			value *= prime;
	}

	// Returns the contribution of this term to the phi calculation.
	public long phi() {
		return value - value/prime;
	}

	public String toString() {
		return prime+"^"+exp+" ";
	}
}