#include <fstream>

using namespace std;
using ll=long long;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int N=1e6+2;
const int M=1e2+2;

ll i,j,o,x,y,m,d,l,k,t,r,s;
ll v[N],p[N],a[M];

int main()
{
	for(i=2,m=N-1, fin>>o; i<=m; i++)
		if(!v[i])
			for(p[++d]=i, j=i*i; j<=m; j+=i)
				v[j]=1;
	while(o--)
    {
		for(fin>>x>>y,l=x, k=0, i=1; i*i<=y; i++)
			if(y%p[i]==0)
				for(a[++k]=p[i]; y%p[i]==0; y/=p[i]);
                    if(y>1)
                        a[++k]=y;
		for(t=1<<k,i=1; i<t; i++)
		{
			for(r=1,s=j=0; j<k; j++)
				if((i&(1<<j))>0)
					s++,r*=a[j+1];
            l+=((s%2==0?1:-1)*x/r);
		}
		fout<<l<<'\n';
	}
	return 0;
}