#include<bits/stdc++.h>
using namespace std;
ifstream F("pinex.in");
ofstream G("pinex.out");
bitset<1000001> b;
int m,n=1e6,a[78498],i,j,k,l;
long long c,d,e[12],q,r,p;
int main()
{
    for(i=3;i*i<=n;i+=2)
        if(!b[i])
            for(j=i*i;j<=n;b[j]=1,j+=2*i);
    for(a[k++]=2,i=3;i<=n;i+=2)
        if(!b[i])
            a[k++]=i;
    for(F>>m;m--;G<<c-r+q<<'\n') {
        for(F>>c>>d,l=0,i=0;i<k&&a[i]*a[i]<=d;++i)
            if(d%a[i]==0)
                for(e[l++]=a[i],d/=a[i];d%a[i]==0;d/=a[i]);
        if(d>1)
            e[l++]=d;
        for(q=r=0,i=1;i<1<<l;++i) {
            for(p=1,j=0;j<l;++j)
                if(i&(1<<j))
                    p*=e[j];
            __builtin_popcount(i)&1?r+=c/p:q+=c/p;
        }
    }
	return 0;
}