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