#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool viz[1002000];
long long t, a, b, v[1000200],k, aux, ans, ok;
vector<long long>d;
int main()
{

    cin>>t;
    for(int o=1;o<=t;++o)
    {
        cin>>a>>b;
        int dd=2;
        d.push_back(1);
        while(b!=1)
        {
            if(b%dd==0)
            {
                while(b%dd==0)
                    b=b/dd;
                d.push_back(dd);
            }
            ++dd;
            if(dd*dd>b)
                dd=b;
        }

        while(viz[0]==0)
        {
            aux=1;
            ok=0;

            for(int i=1;i<d.size();++i)
                if(viz[i]==1)
                {
                    aux=aux*d[i];
                    ++ok;
                }

            if(ok%2==1)
                ans-=a/aux;
            else ans+=a/aux;

            for(k=d.size()-1;k>=0 && viz[k]==1;--k)
                viz[k]=0;
            viz[k]=1;
        }

        cout<<ans<<'\n';

        ans=0;
        d.clear();
    }


    return 0;
}