#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[11],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<<'\n') {
        for(l=i=0,F>>c>>d;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(r=0,i=1;i<1<<l;r+=__builtin_popcount(i)&1?c/p:-c/p,++i)
            for(p=1,j=0;j<l;++j)
                if(i&(1<<j))
                    p*=e[j];
    }
	return 0;
}