#include <stdio.h>
#include <math.h>
#define NMAX 2000023
#define NUM 80023
FILE *fin, *fout;
int n, a, b, c, r[NUM], count, sum, s;
bool sieve[NMAX], ceva[NUM];
int main()
{
	fin = fopen("pinex.in", "r");
	fout = fopen("pinex.out", "w");
	fscanf(fin, "%d", &n);
	for(int i = 2; i< NMAX; i++)
	{
		if(sieve[i]) continue;
		for(int j = 2; j< NMAX; j++)
		{
			if(i*j >= NMAX) break;
			sieve[i*j]  =1;
		}
 	}
 	for(int o = 0; o< n; o++)
 	{
 		fscanf(fin, "%d%d", &a, &b);
 		s = a;
 		c = 0;
 		for(int i = 2; i<= sqrt(b); i++)
 		{
 			if(sieve[i]) continue;
 			if(!(b%i))
 			{
 				if(i == sqrt(b))
 				{
 					r[c] = i;
 					c++;
 					continue;
 				}
 				r[c] = i;
 				c++;
 				if(sieve[b/i]) continue;
 				r[c] = b/i;
 				c++;
 			}
 			if(!sieve[b])
 			{
 				r[c] = b;
 				c++;
 			}
 		}
 		count = 0;
 		for(long long int i = 1; i< pow(2, c); i++)
 		{
			 long long int temp = i;
 			for(int j = 0; j< c; j++) ceva[j] = 0;
 			count = 0;
 			for(int j = c-1; temp; j--)
 			{
				 ceva[j] = temp%2;
 				if(ceva[j]) count++;
 				temp/=2;
 			}
 			sum = 1;
 			for(int j =0; j< c; j++)
 			{
 				if(!ceva[j]) continue;
 				sum*=r[j];
 			}
 			if(count%2) s -= (a/sum);
 			else s += a/sum;
 		}
 		fprintf(fout, "%d\n", s);
 	}
	fclose(fin);
	fclose(fout);
	return 0;
}