#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int lim=1e6;
bool c[lim+10];
int v[lim+10];
int cv[20];
vector <int> t;
int a,b,Q,k,ans,viz[20];
void precalc()
{
    int i,j;
    c[0]=1;
    c[1]=1;
    for(i=2; 2*i<=lim; i++)
        if(c[i]==0)
        {
            for(j=2; j*i<=lim; j++)
                c[i*j]=1;
        }
    for(i=2; i<=lim; i++)
        if(c[i]==0)v[++k]=i;
}
void desc(int nr)
{
    int par;
    for(par=1; par<=k&&v[par]<=nr; par++)
        if(nr%v[par]==0)t.push_back(v[par]);
}
void cnt(int pos)
{
    int i,p=1;
    for(i=1; i<=pos; i++)
    {
        p*=t[cv[i]];
    }
    if(pos%2==0)
    ans+=(int)(a/p);
    else
        ans-=(int)(a/p);
}
bool verif(int pos)
{
    int i;
    for(i=1;i<=pos-1;i++)
        if(t[cv[i]]>t[cv[i+1]])
            return 0;
        return 1;
}
void bkt(int pos)
{
    int i;
    for(i=0; i<t.size(); i++)
    {
        if(viz[i]==0)
        {
            cv[pos]=i;
            viz[i]=1;
            if(verif(pos))cnt(pos);
            if(pos<t.size())
                bkt(pos+1);
            viz[i]=0;
        }
    }
}
void solve()
{
    fin>>a>>b;
    t.clear();
    desc(b);
    ans=a;
    bkt(1);
    fout<<ans<<'\n';
}
int main()
{
    precalc();
    fin>>Q;
    while(Q--)
    {
        solve();
    }
    return 0;
}