#include <fstream>
//#include <iostream>
#include <math.h>

using namespace std;
ifstream ka("pinex.in");
ofstream ki("pinex.out");

const int N_MAX = 1000000;

int m;
long long a, b;
bool compus[N_MAX + 1];
long long fact[N_MAX + 1];

int main()
{
	ka >> m;
	while(m--)
	{
		ka >> a >> b;
		int t = (int)sqrt(b);
		for(int i = 3; i <= t; i += 2)
			for(int j = i * i; j <= t; j += i)
				compus[j] = true;
		fact[0] = 0;
		for(int i = 2; i <= t; i++)
			if(!compus[i] && (b % i == 0))
			{
				fact[++fact[0]] = i;				
				while(b % i == 0)
					b /= 1LL * i;
			}
		if(b > 1)
			fact[++fact[0]] = b;
		/*for(int i = 1; i <= fact[0]; i++)
			cout << fact[i] << " ";
		cout << '\n';*/
		int tt = fact[0];
		long long sol = a;
		for(int i = 1; i < (1 << tt); i++)
		{
			long long nr = 0, prod = 1;
			for(int j = 0; j < tt; j++)
				if(i & (1 << j))
				{
					prod = 1LL * prod * fact[j + 1];
					nr++;
				}
			if(nr % 2 == 1)
				nr = -1;
			else
				nr = 1;
			sol += 1LL * nr * a / prod;
		}
		for(int i = 1; i <= t; i++)
			compus[i] = false;
		ki << sol << '\n';
	}
}