#include<bits/stdc++.h>
using namespace std;
long long d[500],b,a,t, c[100000],cn,cd;
bool ciur[1000200]; 
int main()
{
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	cin >> t;
	for(int i = 2; i<= 1000100; i++)
	{
		if(!ciur[i])
		{
			c[cn] = i;
			cn++;
			for(int j = i; j <= 1000100;j+=i)
			{
				ciur[j] = 1;
			}
		}
	}
	while(t--)
	{
		long long rez = 0;
		cin >> a >> b;
		int cd = 0;
		for(int i = 0; i < cn && b != 1; i++)
		{
			if(b%c[i] == 0)
			{
				d[cd] = c[i];
				cd++;
				while(b%c[i] ==  0 && b > 1)b/=c[i];
			}
		}
		if(b != 1) {
			d[cd] = b;
			cd++;
		}
		for(int i = 0; i < 1 << cd; i++)
		{
			long long k = 0, num = 1;
			for(int j = 0; j < cd; j++)
			{
				if((1<<j) & i)
				{
					num *= 1LL*d[j];
					k++; 
				}
			}
			if (k%2) rez -= a/num;
			else rez += a/num;
		}
	//	int brut = 0;
	//	for(int i =1; i <= a; i++) if (__gcd(i,aux) == 1) brut++;
	//	cout << brut << " ";
		cout << rez << "\n";
	}
}