设gcd(a,m)=xgcd(a,m)=x ，有a=k1x,m=k2x
又知道gcd(a+b,m)=x，有a+b=k3
现在问题就变成了，在闭区间内[k1,k1+k2−1]内有多少个与k2 互质
拆成前缀问题 ,对n 分解质因数后对因子容斥原理即可

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline LL read()
{
    LL x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int T;
LL a,m,x,k1,k2;
LL gcd(LL a,LL b){return b==0 ? a : gcd(b,a%b);}
#include<vector>
vector<LL> pme;
LL count_prime(LL x,LL n){
    pme.clear();
    LL i,j;
    for(i=2;i*i<=n;i++)
        if(n%i==0){
            pme.push_back(i);
            while(n%i==0)n/=i;
        }
    if(n>1)pme.push_back(n);
    LL sum=0,value,cnt;
    for(i=1;i<(1<<pme.size());i++){
        value=1;
        cnt=0;
        for(j=0;j<pme.size();j++){
            if(i&(1<<j)){
                value*=pme[j];
                cnt++;
            }
        }
        if(cnt&1)
            sum+=x/value;
        else sum-=x/value;
    }
    return x-sum;
}
int main()
{
    T=(int)read();
    while(T--)
    {
        a=read();m=read();
        x=gcd(a,m);
        k1=a/x;k2=m/x;
        cout<<count_prime(k2+k1-1,k2)-count_prime(k1-1,k2)<<endl;
    }
    return 0;
}