#include <bits/stdc++.h>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long n,q,numbers,k,nr,j,i,prod,A,B,d,t,prim[1000001],v[101];
bool ciur[1000001];
int main()
{

    ciur[1]=ciur[0]=1;
    for(d=2;d<=1000000;d++)
    {
        if(ciur[d]==0)
        {
            q++;
            prim[q]=d;
            for(i=d*d;i<=1000000;i+=d)
                ciur[i]=1;
        }
    }

    f>>n;
    for(i=1;i<=n;i++)
    {
        numbers=0;t=0;
        f>>A>>B;

        d=1;
        while(prim[d]*prim[d]<=B)
        {
            if(B%prim[d]==0)
            {
                t++;
                v[t]=prim[d];
                while(B%prim[d]==0)B/=prim[d];
            }
            d++;
        }
        if(B!=1)t++,v[t]=B;

        for(k=1;k<(1<<t);k++)
        {
            nr=0;
            prod=1;

            for(j=0;j<t;j++)
            {
                if((k&(1<<j))!=0)
                {
                    nr++;
                    prod=prod*v[j+1];
                }
            }

            if(nr%2==1)numbers+=A/prod;
            else numbers-=A/prod;
        }

        g<<A-numbers<<'\n';
    }
    return 0;
}