#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int lim=1e6;
bool c[lim+10];
int v[lim+10];
vector <int> t;
vector <int> sol;
int a,b,Q,k,ans,pos;
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=0;i<sol.size(); i++)
    {
        p*=sol[i];
    }
    if(pos%2==0)
    ans+=(int)(a/p);
    else
        ans-=(int)(a/p);
}
void bkt()
{
    int i,j,l=t.size();
    for(i=1;i<(1<<l);i++)
    {
        sol.clear();
        for(j=0;j<l;j++)
            if(i&(1<<j))
                sol.push_back(t[j]);
        cnt(sol.size());
    }
}
void solve()
{
    fin>>a>>b;
    t.clear();
    desc(b);
    ans=a;
    pos=0;
    bkt();
    fout<<ans<<'\n';
}
signed main()
{
    precalc();
    fin>>Q;
    while(Q--)
    {
        solve();
    }
    return 0;
}