#include<cstdio>
    #include<vector>
    #include<fstream>
    using namespace std;
    #define pb push_back
    #define MAX 1000100
    #define ll long long
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    int M ;
    vector<ll> p,d;
    bool v[MAX];
    ll sol , A , B ,prod;

    void ciur();
    void solve(ll A , ll B);

    int main()
    {
        ciur();
        f>>M;
        for(;M;--M)
        {
            f>>A>>B;
            solve(A,B);
        }
        f.close();
        g.close();
        return 0;
    }

    void ciur()
    {
        p.pb(2);
        for(int i = 3 ; i <= MAX ; i+=2)
        {
            if(v[i])continue;
            p.pb(i);
            for(int j = i*i ; j <= MAX && j >0 ; j += (i<<1))
                v[j] = 1;
        }
    }

    void solve(ll A , ll B)
    {
        d.clear();
        for( int j = 0 ;1ll* p[j]*p[j] <= B &&j <(int)p.size(); ++j)
            if(B%p[j]==0)
            {
                d.pb(p[j]);
                while(B%p[j]==0)
                    B/=p[j];
            }
        if(B>1)d.pb(B);
        int k = d.size(),nr;
        sol = A;
        for(ll i = 1 ; i< (1<<k) ; ++i)
        {
            nr = 0;
            prod = 1;
            for(int j = 0 ; j<k ; ++j)
                if(i&(1<<j))
                    prod = 1LL*prod*d[j],nr++;
            if(nr%2)sol=sol-1ll*A/prod;
            else sol=sol+1ll*A/prod;
        }
        g<<sol<<"\n";
    }