#include <cstdio>
#include <cstdlib>

FILE *fin=fopen("pinex.in","r");
FILE *fout=fopen("pinex.out","w");

int prim[180000];
int nprime=0;
int cr[1000000];
char p[1000000/8/2+1];

void ciur(int n)
{
	int i, j;
	for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1) {     
		if ((p[i >> 3] & (1 << (i & 7))) == 0) {
			for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {
				p[j >> 3] |= (1 << (j & 7));
			}
		}
	}
	prim[nprime++]=2;
	for (i = 1; 2 * i + 1 <= n; ++i) 
		if ((p[i >> 3] & (1 << (i & 7))) == 0)
			prim[nprime++]=2*i+1;
}

long long solve(long long a, long long b)
{
	int fact[30];
	int nf=0;
	int p=0;
	while (b!=1)
	{
		if (!(b%prim[p]))
		{
			b/=prim[p];
			while (!(b%prim[p]))
				b/=prim[p];
			fact[nf++]=prim[p];
		}
		p++;
		if (p>=nprime)
			break;
	}
	if (b!=1)
		fact[nf++]=b;
	long long sum=a;
	for (int i=1; i<(1<<nf); i++)
	{
		long long nr=1;
		bool par=true;
		for (int j=0; j<nf; j++)
			if (i&(1<<j))
			{
				par=!par;
				nr*=fact[j];
			}
		sum+=(a/nr)*(par?(1):(-1));
	}
	return sum;
}

int main (int argc, char * const argv[]) {
	int m;
	fscanf(fin, "%d",&m);
	ciur(1000000);
	for (int i=0; i<m; i++)
	{
		long long a,b;
		fscanf(fin, "%lld%lld", &a,&b);
		fprintf(fout, "%lld\n",solve(a,b));
	}
	fclose(fin);
	fclose(fout);
    return 0;
}