#include <fstream>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int LIM=1000100;
int prime[LIM+100],np;
long long p[30];
void ciur()
{
    int last=0,i;
    prime[++last]=2;
    for(i=3;i*i<=LIM;i+=2)
        if(prime[i]==0)
        {
            prime[++last]=i;
            for(int j=i*i;j<=LIM;j+=(i+i))
                prime[j]=1;
        }
    for(;i<=LIM;i+=2)
        if(prime[i]==0)
            prime[++last]=i;
}
int main()
{
    int t;
    fin>>t;
    ciur();
    while(t--)
    {
        long long a,b;
        fin>>a>>b;
        np=0;
        int f=1;
        while(b!=1)
        {
            int ok=0;
            if(prime[f]*prime[f]>b) p[++np]=b,b=1;
            while(b%prime[f]==0)
            {
                ok=1;
                b/=prime[f];
            }
            if(ok) p[++np]=prime[f];
            f++;
        }
        long long lim=1;
        for(int i=1;i<=np;++i) lim<<=1;
        long long rez=0;
        for(int i=1;i<lim;++i)
        {
            int cop=i,nb=0,care=1;
            long long prod=1;
            while(cop)
            {
                if(cop&1)
                {
                    nb++;
                    prod*=p[care];
                }
                cop>>=1;
                care++;
            }
            if(nb%2==0) prod*=-1;
            rez+=a/prod;
        }
        fout<<a-rez<<'\n';
    }
    return 0;
}