#include<fstream>
#define N 1000001
using namespace std;
long long v[N],p[N],a[50],i,j,o,x,y,s,r,d,k,t,m,l;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int main() {
    for(m=N-1,i=2,fin>>o; i<=m; i++)
        if(!v[i])
            for(p[++d]=i,j=i*i; j<=m; j+=i)
                v[j]=1;
    while(o--) {
        for(fin>>x>>y,l=x,k=0,i=1; i*i<=y; i++)
            if(y%p[i]==0)
                for(a[++k]=p[i]; y%p[i]==0; y/=p[i]);
        if(y>1)
            a[++k]=y;
        for(t=1<<k,i=1; i<t; i++) {
            for(r=1,s=j=0; j<k; j++)
                if((i&(1<<j))>0)
                    s++,r*=a[j+1];
            l+=((s%2==0?1:-1)*x/r);
        }
        fout<<l<<"\n";
    }
}