#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int N=1e6;
int q,a,b,i,j,sz,sz_prim,ciur[N+5];
vector<int> p;
int solve(int a,int b)
{
    vector<int> v;
    int f[15];
    int i=0,c=b;
    while(p[i]*p[i]<=c)
    {
        if(c%p[i]==0) v.push_back(p[i]);
        while(c%p[i]==0) c/=p[i];
        i++;
        if(i>=sz_prim) break;
    }
    if(c)
    {
        v.push_back(c);
    }
    sz=v.size();
    int p=1,t=a,cnt=0;
    for(i=0;i<sz;++i)
    {
        f[i]=0;
    }
    for(i=1;i<(1<<sz);++i)
    {
        for(j=0;j<=sz;++j)
        {
            if(!f[j]) {p*=v[j]; cnt++; f[j]=1; break;}
            else {cnt--; p/=v[j]; f[j]=0;}
        }
        //cout<<p<<'\n';
        if(cnt&1) t-=(a/p);
        else t+=(a/p);
    }
    return t;
}
void precalc(int lim)
{
    int i,j;
    for(i=2;i*i<=lim;++i)
    if(!ciur[i])
    for(j=i*i;j<=lim;j+=i)
    {
        ciur[j]=1;
    }
    for(i=2;i<=lim;++i)
    {
        if(!ciur[i])
            p.push_back(i);
    }
    sz_prim=p.size();
}
signed main()
{
    precalc(1e6);
    fin>>q;
    while(q--)
    {
        fin>>a>>b;
        fout<<solve(a,b)<<'\n';
    }
    return 0;
}