Rose

有趣的小东西。

显然的想法就是先两个数都除一下gcd，然后剩下两个树=数要互质。

结合一下剩余系的知识，可以知道$[x,x+m]$这m+1个数中，$\psi m^{'}$个数字和m的gcd为1

那就是欧拉函数求一波呗.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int t;
int a;
int m;
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int work(int x){
    int ans=x;
    for(int i=2;i*i<=x;++i){
        if(x%i==0){
            ans=ans/i*(i-1ll);
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1){
        ans=ans/x*(x-1ll);
    }
    return ans;
}
signed main(){
    read(t);
    while(t--){
        read(a);read(m);
        printf("%lld\n",work(m/gcd(a,m)));
    }
    return 0;
}