#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define nmax 1000001
long long i,j,n,k,a,b,nr,rez,nrc,v[100001],prim[100001];
bool p[nmax];
int main()
{
    for(i=4; i<=nmax; i+=2)p[i]=1;
    prim[++nr]=2;
    for(i=3; i<=nmax; i+=2)
    {
        if(p[i]==0)
        {
            prim[++nr]=i;
            for(j=3*i; j<=nmax; j+=i)
            {
                p[j]=1;

            }
        }
    }
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>a>>b;
        int m=0;
        for(j=1; j<=nr&&prim[j]<=b; j++)
        {
            if(b%prim[j]==0)
            {
                v[++m]=prim[j];
            }
        }
        int nn=1<<m;
        rez=a;
        for(j=1; j<nn; j++)
        {
            nrc=0;
            long long   pp=1;
            for(k=0; k<m; k++)
            {
                if(j&(1LL<<k))
                {
                    nrc++;
                    pp=pp*v[k+1];
                }
            }
            if(nrc%2==1)rez=rez-a/pp;
            else rez+=a/pp;

        }
        fout<<rez<<'\n';
    }
    return 0;
}