// Principiul includerii si excluderii.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <vector>
#define LIM 1000006 // = sqrt(10^12)
#define MAXP 80499 // 78499
std::ifstream fin("pinex.in");
std::ofstream fout("pinex.out");
using namespace std;
typedef long long ll;

char ciur[LIM + 1];
ll p = 0, dictionary[MAXP];

ll A, B;
vector<int> vp;
ll ans = 0;

static inline void Eratostene()
{
	for (int i = 0; i <= LIM; i++)
		ciur[i] = '1';
	ciur[0] = ciur[1] = '0';
	for (int i = 4; i <= LIM; i += 2)
		ciur[i] = '0';
	for (int i = 3; i * i <= LIM; i += 2)
		if (ciur[i] == '1')
			for (int j = i; j * i <= LIM; j += 2)
				ciur[j * i] = '0';

	dictionary[p++] = 2;
	for (int i = 3; i <= LIM; i += 2)
		if (ciur[i] == '1')
			dictionary[p++] = i;
}

void FindPrimes(ll x)
{
	ll exp;
	for (ll i = 0; i < p && dictionary[i] * dictionary[i] <= x; i++)
	{
		for (exp = 0; x % dictionary[i] == 0; x /= dictionary[i], exp++);
		if (exp)
			vp.push_back(dictionary[i]);
	}
	if (x > 1)
		vp.push_back(x);
}

void PExclusionInclusion()
{
	ll N = vp.size();
	for (ll bitmask = 1; bitmask <= (1 << N) - 1; bitmask++)
	{
		ll cnt = 0, prod = 1;
		for (ll i = 0; i < N; i++)
			if ((bitmask & (1 << i)) != 0) {
				prod *= vp[i];
				cnt++;
			}
		if (cnt % 2 != 0)
			ans += (A / prod);
		else
			ans -= (A / prod);
	}
}

static inline void Solve()
{
	ans = 0;
	vp.clear();
	FindPrimes(B);
	PExclusionInclusion();
	fout << A - ans << "\n";
}

int main()
{
	Eratostene();
	ll M;
	for (fin >> M; M--;)
	{
		fin >> A >> B;
		Solve();
	}
	return 0;
}