#include<stdio.h>
#include<iostream>
#include<math.h>
#include<vector>

#define ull unsigned long long
using namespace std;
#define N 1000030
ull n, m, t;

ull a[N];
vector<ull> d(0);

void initializare()
{
	ull sqr = sqrt(N);
	
	a[0] =a[1]= 1;
	
	for (ull i = 2; i < N; i++)
	{
		if (a[i] == 0)
		{
			d.push_back(i);
			for (ull j = i*i; j < N; j +=  i)
			{
				if(a[j]==0)
					a[j] = i;
			}
		}
		if (a[i] == 0)
		{
			//printf("%d\n", i);
		}
	}
}

ull pise(vector<ull> &b, ull x, ull numbers_taken, ull number,ull product,ull poz)
{
	ull sum = 0;
	if (numbers_taken == number)
	{
		return x / product;
	}
	else
	{
		
		for (ull i = poz; i < b.size(); i++)
		{
			sum += pise(b, x, numbers_taken + 1, number, product*b[i], i + 1);
		}
	}
	return sum;
}
ull solve(ull x, ull y)
{
	vector<ull> b(0);
	
	int index = 0;
	while (y != 1 && index < d.size())
	{
		if (y%d[index] == 0)
		{
			b.push_back(d[index]);

			while (y%d[index] == 0)
			{
				y /= d[index];
			}
		}
		index++;
	}
	if (y != 1)
		b.push_back(y);

	ull sum = 0;
	for (ull i = 1; i <= b.size(); i++)
	{
		if(i%2==1)
			sum += pise(b, x, 0, i, 1, 0);
		else
			sum -= pise(b, x, 0, i, 1, 0);
	}
	return x-sum;
}
int main()
{
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	scanf("%d", &t);
	
	initializare();
	for (ull i = 1; i <=t; i++)
	{
		ull x, y;
		scanf("%llu %llu", &x, &y);
		printf("%llu\n", solve(x, y));
	}
}