#include <bits/stdc++.h>

using namespace std;

int_fast64_t  m,t,prim[1000001],v[1000001],n;
int_fast64_t rasp,j,i;
int_fast64_t v2[25],a,b;

void bkt(int poz,int_fast64_t p,int nr)
{
    if(poz>m)
    {
        if(p==1)
        {
            return;
        }
        if(nr%2==0)
        {
            rasp-=a/p;
        }
        else
        {
            rasp+=a/p;
        }
        return;
    }
    bkt(poz+1,p*v2[poz],nr+1);
    bkt(poz+1,p,nr);
}

int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    fin>>t;
    for(i=2; i<=1000000; ++i)
    {
        if(prim[i]==0)
        {
            v[++n]=i;
            if(i*i<=1000000)
            {
                for(j=i*i; j<=1000000; j+=i)
                {
                    prim[j]=1;
                }
            }
        }
    }
    while(t--)
    {
        fin>>a>>b;
        m=0;
        rasp=0;
        for(i=1; i<=n && v[i]*v[i]<=b; i++)
        {
            if(b%v[i]==0)
            {
                m++;
                v2[m]=v[i];
                while(b%v[i]==0)
                {
                    b/=v[i];
                }
            }
        }
        if(b!=1)
        {
            m++;
            v2[m]=b;
            b=1;
        }
        bkt(1,1,0);
        fout<<a-rasp<<"\n";
    }
    return 0;
}