给定两个正整数 a,m，其中 a<m。

请你计算，有多少个小于 m 的非负整数 x 满足：

 

gcd(a,m)=gcd(a+x,m)

 

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含两个整数 a,m。

输出格式

每组数据输出一行结果，一个整数，表示满足条件的非负整数 x 的个数。

数据范围

前三个测试点满足，1≤T≤10
所有测试点满足，1≤T≤50，1≤a<m≤10^10

输入样例：

3
4 9
5 10
42 9999999967

输出样例：

6
1
9999999966


欧拉数：表示1~N的有多少个数与N互质

 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL T;

LL gcd(LL a, LL b)
{
   return b?gcd(b,a%b):a;
}

LL phi(LL n)  //求与n互质且小于n的数的个数
{
    LL res = n;
    for (int i = 2; i <= n / i; i ++ )
    {
        if (n % i == 0) res = res / i * (i - 1);
        while (n % i == 0) n /= i; 
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

int main()
{
    scanf("%lld", &T);
    while (T -- )
    {
        LL a, m;
        scanf("%lld %lld", &a, &m);
        LL gcd = _gcd(a, m);
        LL ans = phi(m / gcd);

        printf("%lld\n", ans);
    }

    return 0;
}