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