#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

void descomp(ll b, vector <int> &a)
{
    for(int d=2; d*d<=b; d++)
    {
        if(b%d==0)
        {
            a.pb(d);
            while(b%d==0)
                b/=d;
        }
    }
    if(b!=1)
        a.pb(b);
}

int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");

    int q;
    cin>>q;
    while(q--)
    {
        ll a, b;
        vector <int> primes;
        cin>>a>>b;
        descomp(b, primes);

        int sz=primes.size();
        ll ans=0;
        for(ll mask=1; mask<(1<<sz); mask++)
        {
            ll fac=1, cnt=0;
            for(int b=0; b<sz; b++)
            {
                if(mask&(1<<b))
                {
                    cnt++;
                    fac*=primes[b];
                }
            }
            ans+=(a/fac)*((cnt&1) ? 1LL:-1LL);
        }
        cout<<a-ans<<'\n';
    }

    return 0;
}