#include <fstream>

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
char ciur[1000001];
long long p[80001],v[20],rez,a;
int k=1,t;
void ciuruire()
{
    int i,j;
    p[k]=2;
    for(i=3;i<=1000;i+=2)
        if(ciur[i]==0)
            for(j=i*i;j<=1000000;j+=(i<<1))
                ciur[j]=1;
    for(i=3;i<=1000000;i+=2)
        if(ciur[i]==0)
            p[++k]=i;
}
void bkt(int p, int nr, long long prod)
{
    if(p<=t)
    {
        bkt(p+1,nr,prod);
        bkt(p+1,nr+1,prod*v[p]);
    }
    else
    if(nr>0)
    {
        if((nr&1)==0)
            rez-=a/prod;
        else
            rez+=a/prod;
    }
}
int main()
{
    ciuruire();
    int m,i;
    long long b;
    cin>>m;
    while(m>0)
    {
        m--;
        cin>>a>>b;
        t=0;
        for(i=1;p[i]*p[i]<=b;i++)
        {
            if(b%p[i]==0)
            {
                while(b%p[i]==0)
                    b/=p[i];
                v[++t]=p[i];
            }
        }
        if(b>1)
            v[++t]=b;
        rez=0;
        bkt(1,0,1LL);
        cout<<a-rez<<'\n';
    }
    return 0;
}