三十 3999. 最大公约数 (欧拉函数)

3999. 最大公约数 (欧拉函数)

import java.util.*;

public class Main {
    private static int T;
    private static long a, m;
    
    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    private static long euler(long x) {
        long res = x;
        for(long i = 2; i <= x / i; i++) {
            if((x % i) == 0) {
                while((x % i) == 0) {
                    x /= i;
                }
                res = res / i * (i - 1);
            }
        }
        if(x > 1) {
            res = res / x * (x - 1);
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        while (T-- > 0) {
            a = sc.nextLong();
            m = sc.nextLong();
            long t = gcd(a, m);
            System.out.println(euler(m / t));
        }
    }
}