#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

#define NM 2000005
#define PMAX 2000000

int prime[NM];
long long pr[NM];
bool e_prim[NM];

long long A, B, ans;

void back (int pas, long long div, int cate)
{
	if (pas == pr[0] + 1)
	{
		/*
		if (cate % 2) ans -= A/div;
		else ans += A/div;
		*/
		
		if (div == 1) return ;
		
		ans += (cate % 2 ? -A/div : A/div);
		return ;
	}
	
	back (pas + 1, div, cate);
	back (pas + 1, div * pr[pas], cate + 1);
}

int main()
{
	freopen ("pinex.in", "r", stdin);
	freopen ("pinex.out", "w", stdout);
	
	for (int i = 2; i <= PMAX; ++i) e_prim[i] = true;
	
	for (int i = 2; i <= PMAX; ++i)
		if (e_prim[i])
		{
			prime[++prime[0]] = i;
			for (int j = 2 * i; j <= PMAX; j += i) e_prim[j] = false;
		}	
		
	int T;
	
	scanf ("%d", &T);
	
	while (T--)
	{
		scanf ("%lld %lld", &A, &B);
		
		ans = A;
		int ind = 1;
		int sq = (int)sqrt((long double)B);
		
		long long cB = B;	
		pr[0] = 0;
		
		while (ind <= prime[0] && prime[ind] <= sq && cB != 1)
		{
			if (cB % prime[ind])
			{
				++ind;
				continue;
			}
			
			pr[++pr[0]] = prime[ind];
			while (!(cB % prime[ind])) cB /= prime[ind];
		}	
		
		
		if (cB != 1) pr[++pr[0]] = cB;
		
		/*
		for (int i = 1; i <= pr[0]; ++i) printf ("%d ", pr[i]);
		printf ("\n");
		*/
		
		back (1, 1, 0);
		
		printf ("%lld\n", ans);
	}	
	
	return 0;
}