#include<cstdio>
    #include<vector>
    using namespace std;
    #define pb push_back
    #define MAX 1000100
    #define ll long long
    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();
        freopen("pinex.in" , "r" , stdin );
        freopen("pinex.out" , "w" , stdout );
        scanf("%d" , &M);
        for(;M;--M)
        {
            scanf("%lld%lld" , &A , &B);
            solve(A,B);
        }
        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)
            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 = 0;
        for(int i = 1 ; i< (1<<k) ; ++i)
        {
            nr = 0;
            prod = 1;
            for(int j = 0 ; j<k ; ++j)
                if(i&(1<<j))
                    prod *= 1LL*d[j],nr++;
            if(nr%2)sol+=A/prod;
            else sol-=A/prod;
        }
        printf("%lld\n" , A-sol );
    }