#include <bits/stdc++.h>

using namespace std;

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

long long n,numbers,k,nr,j,i,prod,A,B,d,t,v[101];

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

        d=2;
        while(d*d<=B)
        {
            if(B%d==0)
            {
                t++;
                v[t]=d;
                while(B%d==0)B/=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;
}