#include <fstream>


using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int  v[10001];
int p[300000];

int ciur(int n)
{
    v[0]=v[1]=1;

    for(int i=4; i<=n; i+=2)
        v[i]=1;

    for(int i=3; i*i<=n; i+=2)
        if(v[i]==0)
            for(int j=i*i; j<=n; j+=2*i  )
                v[j]=1;
}

long long d[12];

int main()

{
    ciur(1000);
    int cnt=0;
    for(int i=2; i<=1000; i++)
        if(v[i]==0)
        {
            cnt++;
            p[cnt]=i;
        }
    //  p[1].......p[cnt]   cnt=78498
    int m;
    cin>>m;
    while(m)
    {
        long long a, b;
        cin>>a>>b;
        // d[0].....d[k-1] k=nr de divizori primi
        int ind = 1;
        int k=0;
        while(p[ind]*p[ind]<=b && b>1 )
        {
            if(  b%p[ind]==0 )
            {
                while( b%p[ind]==0 )  b/=p[ind];
                d[k]=p[ind];
                k++;

            }
            ind++;
        }
        if(b>1)
        {
            d[k]=b;
            k++;
        }
//        for(int j=0;j<k;j++)
//            cout<<d[j]<<" ";
//        cout<<(1<<1);
//        cout<<endl;
        // d[0].....d[k-1] k=nr de divizori primi
        int x,j,s;
        long long contor,suma=0;
        for(x=1; x<(1<<k); x++)
        {
            contor=0;
            s=0;
            long long div=1;
            for(j=0; j<k; j++)
                if(x&(1<<j))
                {
                    //s+=(a/d[k-j-1]);
                    contor++;
//                    if(j==1)
//                        cout<<"hey";
                    div*=d[k-j-1];
                }
//            if(a==20)
//            {cout<<div<<" ";}
            if(contor%2==0)
                suma-=(a/div);
            else
                suma+=(a/div);
        }
        cout<<a-suma<<endl;
        m--;
    }


    return 0;
}