#include <cstdio>
#include <iostream>
#include <fstream>
#define ll long long
#define DIVMAX 1000010
int M;
ll A, B;
int p[DIVMAX], PRIM = 0;
int d[DIVMAX], NR = 0;
int f[DIVMAX];
ll rez;

void ciur()
{
	bool e[DIVMAX] = {0};
	for(int i = 2 ; i * i <= DIVMAX ; i++)
		if(!e[i])
			for(int j = i * i ; j <= DIVMAX ; j += i)
				e[j] = 1;
	for(int i = 2 ; i <= DIVMAX ; i++)
		if(!e[i])
			p[++PRIM] = i;
}

void div()
{
	int i = 1;
	while(B > 1)
	{
		if(B %  p[i] == 0)
		{
			d[++NR] = p[i];
			while(B % p[i] == 0) B /=  p[i];
		}
		
		if( p[i] * p[i] >= B && B > 1)
		{
			d[++NR] = B;
			break;
		}
		
		i++;
	}
}

void back(ll k, ll x, ll scad)
{
	if(k == NR + 1)
	{
		rez += A / x * scad;
		return;
	}
	back(k + 1, x, scad);
	back(k + 1, x * d[k], -scad);
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%d", &M);
	ciur();
	for(int i = 1 ; i <= M ; i++)
	{
		rez = 0;NR = 0;
		scanf("%lld%lld", &A, &B);
		div();
		back(1, 1, 1);
		printf("%lld\n",rez);
	}
	
	return 0;
}