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

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

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);
	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;
}