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

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

int a[N];

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

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

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

	}
	b.push_back(y);

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