#include<stdio.h>
#include<math.h>
#define nmax 100000000

int i,m;
long long a,b,j,k; 
bool prim[nmax];
long long prim2[1000000];
long long cnt[100000];
long long db=0;

void era()
{
	for(j=2;j<=nmax;j++)
		if(prim[j]==false)
		{
			for(k=j+j;k<=nmax;k+=j)
				prim[k]=true;
			prim2[++db]=j;
		}
}

void solve()
{
	cnt[0]=0;
	for(k=1;b>1;k++)
		if(b%prim2[k]==0)
		{
			cnt[++cnt[0]]=prim2[k];
			while(b%prim2[k]==0)
				b=b/prim2[k];
		}
	long long sol=a,p,nr;
	for(i=1;i<(1<<cnt[0]);i++)
	{
		p=1,nr=0;
		for(j=0;j<cnt[0];j++)
			if((1<<j)&i)
			{
				p*=cnt[j+1];
				nr++;
			}
		if(nr%2==1) nr=-1;
		else nr=1;
		sol+=nr*a/p;
	}
	printf("%lld\n", sol);

}


int main()
{
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
	scanf("%d", &m);
	era();
	int i;
	for(i=1;i<=m;i++)
	{
		scanf("%lld %lld", &a, &b);
		solve();
	}
	return 0;
}