#include<fstream.h>
#include<iostream.h>

char v[510000];
int w[200000],nr;

void ciur(int x)
{
	int xx=sqrt(x),gasit,a,b,c,d;
	nr=1;
	d=3;
	w[1]=2;
	while(d<=x)
	{
		w[++nr]=d;
		if(d<=xx)
		{
			a=d*d;
			b=(d<<1);
			while(a<=x)
			{
				v[a>>1]=1;
				a+=b;
			}
		}
		gasit=0;
		c=(d>>1)+1;
		while(!gasit)
		{
			if(!v[c])
			{
				d=(c<<1)+1;
				gasit=1;
			}
			else c++;
			}		
		}
}

int main()
{
	long long max=0,aa[510],bb[510],a,b,fact[30],rez,	prod;
	int i,t,div,nf,p,nr,j;
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	f>>t;
	for(i=1;i<=t;i++)
	{
		f>>aa[i]>>bb[i];
		if(max<bb[i])
			max=bb[i];
	}
	max=sqrt(max);
	ciur(max);
	for(max=1;max<=t;max++)
	{
		a=aa[max];
		b=bb[max];
		rez=a;
		nf=0;
		p=1;
		div=w[p];
		while(div*div<=b)
		{
			if(b%div==0)
			{
				while(b%div==0)
					b/=div;
				fact[++nf]=div;
			}
			div=w[++p];
		}
		if(b>1)
			fact[++nf]=b;
		for(i=1;i<(1<<nf);i++)
		{
			prod=1;
			nr=0;
			for(j=0;(1<<j)<=i;j++)
				if((1<<j)&i)
				{
					prod*=fact[j+1];
					nr++;
				}
			prod=a/prod;	
			if(nr%2)
				prod=-prod;
			rez+=prod;
		}	
		g<<rez<<'\n';
	}	
	return 0;
}