FML

# Solution

Let $g= \gcd(a,m)$, so we have $a=g\cdot k, m=g\cdot l,\gcd(l,k)=1$,first observation is that if we want $\gcd(a,m)=\gcd(a+x,m)$, $x$ has to be a multiple of $g$, let $x=n\cdot g$. Furthermore, $k+n$ and $l$ have to be coprime, so we need to find how many numbers ranging from $k$ to $k+l$ are coprime with $l$. For numbers bigger than $l$, if $\gcd(k+x,l)=1$, then $\gcd((k+x)\bmod l,l)=1$. Since $(k+x)\bmod l< l$, what we actually need to find is the number of numbers that are coprime with $l$ and smaller than $l$, i.e. $\varphi(l)$.

# Code

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

ll Phi(ll m){
ll ans=m;
for(ll i=2;i*i<=m;i++){
if(m%i==0){
ans-=ans/i;
while(m%i==0) m/=i;
}
}
if(m>1) ans-=ans/m;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
cin>>tt;
while(tt--){
ll a,m;
cin>>a>>m;
cout<<Phi(m/gcd(a,m))<<endl;

}
return 0;
}