#include<stdio.h>
#include<vector>
#define tip long long
using namespace std;
vector<tip> D[40];
tip A,B,BC,S,P,n,p[1100000],i,j,np,d;
void read(),solve(),ciur();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%lld",&n);
}
void solve()
{
	vector<tip>::iterator it;
	ciur();D[0].push_back(1);
	for(;n;n--)
	{
		scanf("%lld%lld",&A,&B);
		for(i=1;i<40;i++)D[i].resize(0);
		d=0;BC=B;
		for(i=1;i<=np;i++)
		{
			
			if(BC%p[i]==0)
			{
				P=p[i];d++;
				for(j=d;j>=1;j--)
					for(it=D[j-1].begin();it!=D[j-1].end();it++)
						D[j].push_back(*it*P);
				while(BC%P==0)BC/=P;
			}
			if(BC==1)break;
		}
		if(BC>1)
		{
			P=BC;d++;
			for(j=d;j>=1;j++)
				for(it=D[j-1].begin();it!=D[j-1].end();it++)
					D[j].push_back(*it*P);
		}	
		S=0;
		for(i=0;i<=d;i+=2)
		{
			for(it=D[i].begin();it!=D[i].end();it++)S+=A/(*it);
			for(it=D[i+1].begin();it!=D[i+1].end();it++)S-=A/(*it);
		}
		printf("%lld\n",S);
	}
}
void ciur()
{
	for(i=2;i<=1000;i++)
		if(!p[i])
		{
			p[++np]=i;
			for(j=i*i;j<=1000000;j+=i)
				p[j]=1;
		}
	for(i=1001;i<=1000000;i++)
		if(!p[i])
			p[++np]=i;
}