#include<fstream>
#include<cstring>
#include<bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset<1000001>f;
int w[100];
long long a,b,b1,nr,y,sol,k,k1,i,j,t,m,z[100],v[300000],sol1,q;
int main(){
    fin>>m;
    for(i=2;i<=1000000;i++){
        if(!f[i]){
            v[++t]=i;
            for(j=i+i;j<=1000000;j+=i){
                f[j]=1;
            }
        }
    }
    for(i=1;i<=m;i++){
        fin>>a>>b;
        b1=b;
        k=0;
        for(i=1;v[i]*v[i]<=b&&b1!=1;i++){
            if(b1%v[i] == 0){
                z[++k] = v[i];
                while (b1%v[i]==0){
                    b1/=v[i];
                }
            }
        }
        if(b1!=1){
            z[++k] = b1;
        }
        memset(w, 0, sizeof(w));
        sol=0;
        while(w[0]==0){
            k1=k;
            while(w[k1]==1){
                w[k1] = 0;
                k1--;
            }
            w[k1]=1;
            if (k1==0){
                break;
            }
            q=0;sol1=1;
            for(j=1;j<=k;j++){
                q+=w[j];
                if(w[j]==1){
                    sol1*=z[j];
                }
            }
            if(q%2==1){
                sol+=a/sol1;
            }
            else{
                sol-=a/sol1;
            }
        }
        if(sol>0){
            fout<<a-sol<<"\n";
        }
        else{
            fout<<a+sol<<"\n";
        }
    }
    return 0;
}