//https://www.infoarena.ro/problema/pinex

#ifdef _MSC_VER
	#define _CRT_SECURE_NO_WARNINGS
#elif  __GNUC__
	#pragma GCC optimize("Ofast,unroll-loops,inline")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

//#define _USE_MATH_DEFINES

#include <iostream>
#include <fstream>
#include <utility>
#include <cstdint>
//#include <cstdio>
//#include <algorithm>
#include <vector>
//#include <array>
//#include <list>
//#include <forward_list>
//#include <string>
//#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
//#include <stack>
//#include <map>
//#include <set>
//#include <unordered_map>
//#include <unordered_set>
//#include <limits>
//#include <climits>
//#include <iomanip>
//#include <tuple>
//#include <numeric>
//#include <chrono>
//#include <memory>

using namespace std;

using int64 = int64_t;
using uint64 = uint64_t;
using int16 = int16_t;
using uint16 = uint16_t;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define for0(i,n) for(int i=0; i<(n); ++i)
#define for1(i,n) for(int i=1; i<=(n); ++i)
#define foreach(x,a) for(auto& x : a)
#define cforeach(x,a) for(const auto& x : a)
#define cendl cout << "\n"
#define fendl fout << "\n"
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

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

//freopen("problem.in", "r", stdin);
//freopen("problem.out", "w", stdout);

const int BMAX = 1e6;
const int PMAX = 80000;

bool bPrim[BMAX + 1];
int prim[PMAX], psz; // aici e mai putin

void ciur()
{
	bPrim[0] = bPrim[1] = 1;
	for (int64 i = 2; i <= BMAX; ++i)
	{
		if (!bPrim[i])
		{
			prim[++psz] = i;
			//cout << i << " ";
			if (i * i > BMAX)
				continue;

			for (int64 j = i * i; j <= BMAX; j += i)
				bPrim[j] = 1;
		}
	}
}

int main()
{
	//FASTIO;

	int t, a, b, k, rez;
	vector<int> nrp;

	ciur();

	fin >> t;
	while (t--)
	{
		rez = 0;
		nrp.clear();
		fin >> a >> b;

		k = 1;
		while (k <= psz)
		{
			if (b % prim[k] == 0)
			{
				while (b % prim[k] == 0)
					b /= prim[k];
				nrp.pb(prim[k]);
			}

			++k;
			if (prim[k] * prim[k] > b)
				break;
		}

		if (b != 1)
			nrp.pb(b);

		/*cforeach(it, nrp)
			cout << it << " ";
		_endl;*/

		for (int i = 1; i < (1 << sz(nrp)); ++i)
		{
			int64 div = 1, nd = 0;

			for (int j = 0; j < sz(nrp); ++j)
			{
				if (i & (1 << j))
				{
					div *= nrp[j];
					++nd;
				}
			}
			
			if (nd & 1)
				rez += (a / div);
			else
				rez -= (a / div);
		}
		
		fout << a - rez;
		fendl;
	}

	return 0;
}