#include<fstream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
bitset<1000005> c;
vector<int> p;
void ciur()
{
    int n=1000000,lim=1000;
    for(int i=4;i<=n;i+=2)
        c[i]=true;
    c[0]=c[1]=true;
    for(int i=3;i<=lim;i+=2)
        if(!c[i])
            for(int j=i*i;j<=n;j+=i)
                c[j]=true;
    p.push_back(2);
    for(int i=3;i<=n;i+=2)
        if(!c[i])
            p.push_back(i);
}
long long sqr(long long v)
{
    long long ans=0;
    for(long long pas=1<<20;pas;pas>>=1)
        if(1LL*(ans+pas)*(ans+pas)<=v)
            ans+=pas;
    return ans;
}
void solve()
{
    long long a,b;
    cin>>a>>b;
    vector<long long> d;
    long long lim=sqr(b);
    for(int c=0;p[c]<=lim && b>1;c++)
        if(b%p[c]==0)
        {
            d.push_back(p[c]);
            while(b%p[c]==0)
                b/=p[c];
        }
    if(b>1)
        d.push_back(b);
    long long ans=0;
    for(int i=0;i<(1<<(int)d.size());i++)
    {
        int nr=0;
        long long P=1;
        for(int j=0;j<(int)d.size();j++)
            if(i&(1<<j))
                P*=d[j],
                nr++;
        if(nr&1)
            ans-=a/P;
        else
            ans+=a/P;
    }
    cout<<ans<<'\n';
}
int main()
{
    int T;
    ciur();
    for(cin>>T;T;T--)
        solve();
    return 0;
}