欧拉函数： 一个数n， 从1~n-1中与n互质的数的个数（互质：最大公约数为1）
思路： 对n进行质因数分解 n = p1^k1 * p2^k2 * … * pn^kn
答案： n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pn)
等价： n * (p1 - 1)/p1 * (p2 - 1)/p2 * … * (pn - 1)/pn

一个数n的约数的个数 = (k1 + 1) * (k2 + 1) * … * (kn + 1)
一个数n的约数的和 = (p1^0 + p1^1 + … + p1^k1) * (p2^0 + p2^1 + … + p2^k2) * (pn^0 + pn^1 + … + pn^kn)

import java.io.*;
import java.util.*;
class Main {
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        int t = Integer.valueOf(read.readLine());
        while (t -- > 0){
            int a = Integer.valueOf(read.readLine());
            log.write(getEula(a) + "\n");
        }
        log.flush();
    }


    public static long getEula(int a){
        int t = a;
        Map<Integer, Integer> map = new HashMap();
        for(int i = 2; i <= a / i; i++){
            if(a % i == 0){
                int cnt = 0;
                while (a % i == 0){
                    cnt++;
                    a /= i;
                }
                map.put(i, map.getOrDefault(i, 0) +  cnt);
            }
        }
        if(a > 1) map.put(a, map.getOrDefault(a, 0) + 1);
        long eula = t;
        for(Integer key: map.keySet()){
            eula = eula * (key - 1) / key;
        }
        return eula;
    }

}