#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 d=2;
    while(d*d<=nr)
    {
        int p=0;
        while(nr%d==0)
        {
            nr/=d;
            p++;
        }
        if(p)
        {
            t.push_back(d);
        }
        d++;
    }
    if(nr>1)
        t.push_back(nr);
}
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;
    bkt();
    fout<<ans<<'\n';
}
signed main()
{
    fin>>Q;
    while(Q--)
    {
        solve();
    }
    return 0;
}