#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#define ll long long
#define DIM 1000000

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int t;
bitset <DIM+10> ciur;
vector <ll> aux, prime;

void precalc()
{	for(int i=2; i<=DIM; i++)
		if(!ciur[i])
			{	prime.push_back(i);
				for(int j=2*i; j<=DIM; j+=i)
					ciur[j] = 1;
			}
}

int main()
{	
	precalc();
	fin >> t;
	while(t--)
		{	ll a, b;
			fin >> a >> b;
			ll sq = sqrt(b), x = b;
			aux.clear();
			for(int i=0; prime[i]<=sq && x > 1; i++)
				if(x % prime[i] == 0)
					{	aux.push_back(prime[i]);
						while(x % prime[i] == 0)
							x /= prime[i];
					}
			if(x > 1)
				aux.push_back(x);
			int dim = aux.size();
			ll ans = 0;
			for(int mask=1; mask<(1<<dim); mask++)
				{	int cnt = 0;
					ll p = 1;
					for(int bit=0; bit<dim; bit++)
						if(mask & (1 << bit))
							{	cnt++;
								p *= aux[bit];
							}
					ll nr = a / p;
					if(cnt % 2 == 0)
						ans -= nr;
					else
						ans += nr;
				}
			fout << a - ans << '\n';
		}
	return 0;
}