#include <fstream>

using namespace std;
long long d[100];
int main()
{ long long div,n,x,Max,i,j,nr,t,p,sum;
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    f>>t;
    for (p=1;p<=t;++p) {
        f>>Max>>nr;
        x=nr;
        sum=n=0;
        div=2;
        while (x>1) {
            if (x%div==0) {
                ++n;
                d[n]=div;
                while (x%div==0)
                    x/=div;
            }
            ++div;
        }
        for (i=1;i<=n;++i)
            sum+=Max/d[i];
        for (i=1;i<n;++i)
        for (j=i+1;j<=n;++j)
          sum-=Max/(d[i]*d[j]);
        sum+=Max/nr;
       if (n>2) g<<Max-sum<<'\n';
       else {
          if (n==1) g<<Max-Max/nr<<'\n';
          else g<<Max-(Max/d[1]+Max/d[2]-Max/(d[1]*d[2]))<<'\n';
       }
    }
    return 0;
}