import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
public class Main {
final static int SIZE = 1000000;
static int[] divTab = new int[SIZE + 1];
static ArrayList nextPrime = new ArrayList();
static void makeTable() {
for(int i = 2; i <= SIZE; i++)
divTab[i] = i;
for(int i = 2; i * i <= SIZE; i++)
if (divTab[i] == i) for(int j = i * i; j <= SIZE; j += i)
if (divTab[j] == j) divTab[j] = i;
for(int p = 2; p <= SIZE; p++)
if (divTab[p] == p) nextPrime.add(p);
}
static long[] phiTab = new long[SIZE + 1];
static long phi(long n) {
int nn = (int) n, wynik = 1, p = 0, q, qq;
if (n <= 1) return n;
if (n == 2) return 1;
if (nn < SIZE && phiTab[nn] != 0) return phiTab[nn];
int i = 0;
while (n > 1) {
if (n <= SIZE) p = divTab[(int) n];
else {
// szukamy dzielnika pierwszego liczby n
while (i < nextPrime.size() && n % (p = nextPrime.get(i)) != 0)
i++;
if (i == nextPrime.size()) p = (int) n; // n jest pierwsza
}
q = 1;
qq = p;
n /= p;
while (n % p == 0) {
q = qq;
qq = qq * p;
n = n / p;
}
wynik *= qq - q;
}
if (nn < 1000000) phiTab[nn] = wynik;
return wynik;
}
public static void main(String[] args) throws NumberFormatException, IOException {
makeTable();
int tests = Integer.parseInt(br.readLine());
while (tests-- > 0) {
int n = Integer.parseInt(br.readLine());
out.println(phi(n));
}
out.flush();
}
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static BufferedReader br = (new BufferedReader(new InputStreamReader(System.in)));
}