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

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

unsigned long long a[N];

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

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

		unsigned long long x = a[y];
		
		while (y%x == 0)
		{
			y /= x;
		}

	}
	b.push_back(y);

	unsigned long long sum = 0;
	for (unsigned long long 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 (unsigned long long i = 1; i <=t; i++)
	{
		unsigned long long x, y;
		scanf("%llu %llu", &x, &y);
		printf("%llu\n", solve(x, y));
	}
}