// Arup Guha
// 3/4/2021
// Solution to COP 4516 Team Contest #1 Problem: Affine Cipher

import java.util.*;

public class affine {

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process all cases.
		for (int loop=0; loop<nC; loop++) {
		
			// Get input.
			long n = stdin.nextLong();
			
			// Initial value of phi --> we will reduce it eventually to phi(n).
			long phi = n;
			
			// Use phi formula where you multiply n by (1 - 1/p) for each unique prime divisor.
			int i = 2;
			long saven = n;
			while (i*i <= saven) {
				if (saven%i == 0) phi = phi/i*(i-1);
				while (saven%i == 0) saven /= i;
				i++;
			}
			
			// Take care of the last prime factor.
			if (saven > 1) phi = phi/saven*(saven-1);
		
			// a can take on any of phi(n) values, and b can take on any of the n values.
			System.out.println(phi*n);
		}
	}
}