#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector <int> v;
long long n,i,a,b,f,k,j,t,p,nr,s;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        f=2;
        while(b>1)
        {
            if(b%f==0) v.push_back(f);
            while(b%f==0)
                b/=f;
            f++;
            if(f*f>b) f=b;
        }

        int k=v.size();
        s=a;
        for(j=1;j<(1<<k);j++)
        {
            p=1;
            nr=0;
            for(t=0;t<k;t++)
                if(j&(1<<t))
                    {
                        p=p*v[t];
                        nr++;
                    }
            if(nr%2==0)
                s+=a/p;
            else
                s-=a/p;
        }
        fout<<s<<'\n';
        v.clear();
    }
    return 0;
}