#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int v[1000001],prime[80000],diviz[300],g[300];
int i,j,k,n,d,nr;
long long a,b,aux,total;
int main()
{
    for(i=2; i<1000000; i++)
        if(v[i]==0)
        {
            for(j=i+i; j<1000000; j+=i)
                v[j]=1;
            prime[++k]=i;
        }
    fin>>n;
    for(; n--;)
    {
        fin>>a>>b;
        i=total=0;
        for(d=1; d<=k && b!=1 && prime[d]<=b/prime[d]; d++)
            if(b%prime[d]==0)
            {
                diviz[++i]=prime[d];
                while(b%prime[d]==0)
                    b/=prime[d];
            }
        if(b>1)
            diviz[++i]=b;

        for(j=0; j<20; j++)
            g[j]=0;

        while(!g[0])
        {
            j=i;
            while(j && g[j]==1)
            {
                g[j]=0;
                j--;
            }
            if(j<1)
                break;

            g[j]=1;
            aux=1;
            nr=0;
            for(; j; j--)
                if(g[j]==1)
                {
                    nr++;
                    aux*=diviz[j];
                }
            if(nr%2)
                total+=a/aux;
            else
                total-=a/aux;
        }
        fout<<a-total<<"\n";
    }
}