#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

#define PB push_back

int A, B, ans, bB;

vector <int> fp;

void back (int pas, int c1, int div)
{
	if (pas == fp.size())
	{
		if (div == 1) return ;
		
		//printf ("NNN %d %d\n", bB, A/div);
		
		if (c1 % 2) ans -= A/div;
		else ans += A/div;		
		
		return ;
	}	
	
	for (int i = 0; i <= 1; ++i)
		if (i) back (pas + 1, c1 + 1, div * fp[pas]);
		else back (pas + 1, c1, div);
}

int main()
{
	freopen ("pinex.in", "r", stdin);
	freopen ("pinex.out", "w", stdout);
	
	int T;
	scanf ("%d", &T);
	
	while (T--)
	{
		scanf ("%d %d", &A, &B);
		
		ans = A;
		
		bB = B;
		int sq = (int)sqrt((double)B);
		
		for (int d = 2; d <= sq; ++d)
		{
			if (B == 1) break;
			if (B % d) continue;
			
			int ee = 0;
			
			while (B % d == 0)
			{
				++ee;
				B /= d;
			}	
			
			fp.push_back(d);
			
			//cout << bB<< " "<< d << " " << ee << '\n';
		}	
		
		if (B > 1)
		{
			fp.push_back(B);
			
			//cout << bB<< " "<< B << " " << 1 << '\n';
		}	
		
		back (0, 0, 1);
		
		printf ("%d\n", ans);
		
		fp.clear();
	}	
	
	return 0;
}