#include <bits/stdc++.h>

#define int long long

using namespace std;

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

int n,x,i;

void solve()
{
    fin>>n>>x;
    if(x==1)
    {
        fout<<0<<'\n';
        return;
    }
    int d=2;
    vector<int> p;
    while(x>1)
    {
        bool ok=0;
        while(x%d==0){x/=d;ok=1;}
        if(ok)
            p.push_back(d);
        d++;
        if(x>1&&d*d>x)
            d=x;
    }
    int lim=1<<p.size();
    int ans=n;
    for(i=1;i<lim;i++)
    {
        int semn=1;
        int pr=1;
        if(__builtin_popcount(i)&1)semn=-1;
        for(int j=0;j<p.size();j++)
            if(i&(1<<j))
                pr*=p[j];
        ans+=semn*(n/pr);
    }
    fout<<ans<<'\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    fin>>t;
    while(t--)
        solve();
    return 0;
}