#include <cstdio>
#include <bitset>

using namespace std;
int prim[1000001],fact[30];
bitset <1000001> ciur;
bitset <30> gen;
int main()
{
    FILE *fin=fopen ("pinex.in","r");
    FILE *fout=fopen ("pinex.out","w");
    int i,j,h,fp,e,nrf,elem,m;
    long long a,sol,p,b;
    for (i=2;i<=1000000;i++){
        if (!ciur[i])
            for (j=i+i;j<=1000000;j+=i)
                ciur[j]=1;
    }
    elem=0;
    for (i=2;i<=1000000;i++)
        if (!ciur[i])
            prim[++elem]=i;
    // in prim sunt toate numerele prime pana la 1 milion
    fscanf (fin,"%d",&m);
    for (h=1;h<=m;h++){
        fscanf (fin,"%lld%lld",&a,&b);
        sol=a;
        i=1;
        fp=0;
        while (i<=elem && prim[i]*prim[i]<=b){
            e=0;
            while (b%prim[i]==0){
                b/=prim[i];
                e++;
            }
            if (e)
                fact[++fp]=prim[i];
            i++;
        }
        if (b!=1)
            fact[++fp]=b;
        gen.reset();
        while (!gen[0]){
            i=fp;
            while (gen[i]==1){
                gen[i]=0;
                i--;
            }
            if (i==0)
                break;
            gen[i]=1;
            p=1;
            nrf=0;
            for (i=1;i<=fp;i++)
                if (gen[i]){
                    nrf++;
                    p*=fact[i];
                }
            if (nrf%2==0)
                sol=sol+a/p;
            else sol=sol-a/p;
        }
        fprintf (fout,"%lld\n",sol);
    }
    return 0;
}