#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("pinex.in");
ofstream out("pinex.out");
#define cin in
#define cout out
#endif // LOCAL

#define int long long

int gcd(int a, int b)
{
    while(true)
    {
        a%=b;
        if(a==0) return b;
        swap(a,b);
    }
}


int lcm(int a, int b)
{
    return (a*b)/gcd(a,b);
}
int n;

int mult;
vector<int> prims;
int ans;
int a,b;

void addToSol(int x)
{
    //nu e prim
    if(gcd(mult,x)==x)
    {
        //cout<<"nu e prim "<<x<<"\n";
        int mod=-1;
        for(auto e:prims)
        {
            if(x%e==0) mod=-mod;
        }
        ans+=(a/x)*mod;

    }
    //e prim
    else if(gcd(mult,x)==1)
    {
        // cout<<"e prim "<<x<<"\n";
        ans+=(a/x);
        mult=mult*x;
        prims.push_back(x);
    }
    //are multiplii primi incompatibili
}

void solve()
{
    cin>>a>>b;

    mult=1;
    ans=0;
    prims.clear();

    int d;
    for(d=1;d*d<=b;d++)
    {
        if(b%d==0)
        {
            if(d!=1)addToSol(d);
            //cout<<d<<' '<<ans<<'\n';
        }
    }

    for(d--;d>=1;d--)
    {
        if(b%d==0)
        {
            if(b/d!=d)addToSol(b/d);
            //cout<<b/d<<' '<<ans<<'\n';
        }
    }

    cout<<a-ans<<'\n';
}

int32_t main()
{
    cin>>n;
    while(n--)
    {
        solve();
    }
    return 0;
}