#include <fstream>

using namespace std;

ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

long long prim[100010],v[100010];

long long t,i,k,r,p,n,j,a,b,rez;

bool f[1000005];

int main () {

    for (i=2;i<=1000000;i++) {
        if (f[i]==0) {
            prim[++k]=i;
            for (j=i+i;j<=1000000;j+=i)
                f[j]=1;
        }
    }
    fin>>t;

    while (t--){
        fin>>a>>b;
        k=0;
        for (i=1;prim[i]*prim[i]<=b;i++)
            if (b%prim[i]==0){
                v[++k]=prim[i];
                while (b%prim[i]==0)
                    b/=prim[i];
            }
        if (b!=0)
            v[++k]=b;
        n=1<<k;rez=0;
        for (i=1;i<n;i++) {
            r=0;p=1;
            for (j=1;j<=k;j++)
                if(i&(1<<(j-1))){
                    r++;
                    p*=v[j];
                }
            if (r%2==0)
                rez+=a/p;
            else
                rez-=a/p;
        }
        fout<<a+rez<<"\n";
    }

    return 0;
}