#include <stdio.h>

#define MAX 1000000

int ciur[MAX];
long int A[1001];
int m;
long long a, b;
long int i, j, k, p;
long long suma, tot;

int main ()
{
	FILE *f = fopen ("pinex.in","r");
	FILE *g = fopen ("pinex.out","w");
	fscanf (f,"%d", &m);
	
	for (i=2; i<=MAX; ++i)
		ciur[i] = 1;
	for (i=2; i*i<=MAX; ++i)
		if (ciur[i])
			for (j=2; j*i<=MAX; ++j)
				ciur[i*j] = 0;
	
	for (i=1; i<=m; ++i)
	{
		fscanf (f,"%lld %lld", &a, &b);
		k = 0;
		tot = 1;
		for (j=2; j<=b; ++j)
			if (ciur[j] && b % j == 0)
			{
				k ++;
				A[k] = j;
				tot *= j;
			}
		suma = 0;
		for (j=1; j<=k; ++j)
			suma += (int) a/A[j];
		for (j=1; j<k; ++j)
			for (p=j+1; p<=k; ++p)
				if (j != p)
					suma -= (int) a/(A[j]*A[p]);
		if (k > 2)
			suma += (int) a/tot;
		fprintf (g,"%lld\n", a - suma);
	}

	fclose(g);
	fclose(f);
	return 0;
}