#include<stdio.h>
#include<algorithm>

using namespace std;

FILE*f=fopen("pinex.in","r"),*g=fopen("pinex.out","w");

int c[1000], M, P[100000], nr, A[502], B[502], n;

void ciurul()
{
	for(int i = 2; i * i <= M; i++)
	{
		if(c[i] == 0)
		{
			P[++nr] = i;
			for(int j = i*2; j  <= M ; j+=i)
			{
				c[j] = 1;
			}
		}
	}
}



int main()
{
	fscanf(f,"%d\n",&n);
	for(int i = 1; i <= n ; i++)
	{
		fscanf(f,"%d %d\n",&A[i],&B[i]);
		M = max(M, B[i]);
	}
	
	int div[40], p = 0;
	ciurul();
	for(int i = 1; i <= n; i++)
	{
		int x = B[i], j = 1;
		p =0;
		while(x != 1 && j <= nr )
		{
			if(x % P[j] == 0)
				div[++p] = P[j];
			
			while(x % P[j] == 0)
			{
				x /= P[j]; 
			}
			j++;
		}
		if(x != 1)
		{
			div[++p] = x;
		}	
		
		int sol = 0, pe = 1, ne = 0, s[20];
		for (j = 0; j<=p; j++)
			s[j] = 0;
		
		
		while (s[0] == 0) {
			j = p;
			while (s[j] == 1) {
				s[j] = 0;
				j--;
			}
			s[j] = 1;
			
			if (j==0)
				break;
			
			pe = 1;
			ne = 0;
			for (j=1;j<=p;j++) {
				if (s[j] == 1) {
					pe *= div[j];
					ne++;
				}
			}
			if (ne %2 == 1)
				sol += A[i]/pe;
			else
				sol -= A[i]/pe;
		}
		
		fprintf(g,"%d\n",A[i] - sol);
	}
	
	

return 0;	
}