#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long t,a,b,i,j,k,x,nr,sol,p[100001],v[101],w[101];
bool ciur[1000001];
int main() {
    k=0;
    for (i=2;i<=1000000;i++)
        if (ciur[i]==0) {
            p[++k]=i;
            for (j=2*i;j<=1000000;j+=i)
                ciur[j]=1;
        }
    fin>>t;
    while (t--) {
        fin>>a>>b;
        x=b;
        k=0;
        for (i=1;p[i]*p[i]<=b && x!=1;i++)
            if (x%p[i]==0) {
                v[++k]=p[i];
                while (x%p[i]==0)
                    x/=p[i];
            }
        if (x!=1)
            v[++k]=x;
        memset(w,0,sizeof(w));
        sol=0;
        while (w[0]==0) {
            i=k;
            while (w[i]==1)
                w[i--]=0;
            w[i]=1;
            if (i==0)
                break;
            nr=0;
            x=1;
            for (i=1;i<=k;i++) {
                nr+=w[i];
                if (w[i]!=0)
                    x*=v[i];
            }
            if (nr%2==0)
                sol-=a/x;
            else
                sol+=a/x;
        }
        if (sol>0)
            fout<<a-sol<<"\n";
        else
            fout<<a+sol<<"\n";
    }
    return 0;
}