#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#define nmax 1000005
#define ll long long int
using namespace std;
ifstream f("pinex.in");
ofstream o("pinex.out");
//int i, j;
int m;
pair <ll, ll> cifre;
int v[nmax];
int prime;

int d;
int x[100000];
int prim[80000];
int fact[40];
//int t;
//long long int  prod;
//ll sol = cifre.first;


void erathosthene()
{
	for (size_t i = 2; i <= nmax; i++)
	{

		v[i] = 1;

	}

	for (size_t i = 2; i <= nmax; i++)
	{
		if (v[i])
		{
			prim[++v[0]] = i;
			//cout << prim[v[0]] << " ";

			for (size_t j = 2 * i; j <= nmax; j += i)
			{

				v[j] = 0;
			}

		}
	}
}

void cate() {
	//int t = 0;
	ll t = 1, d = 0;
	while (cifre.second > 1) {
		d++;
		if (cifre.second % prim[d] == 0) {
			fact[++t] = prim[d];
			while (cifre.second % prim[d] == 0)
				cifre.second /= prim[d];
		}

		if (prim[d] > sqrt(cifre.second) && cifre.second > 1) {
			fact[++t] = cifre.second;
			cifre.second = 1;
		}
	}
	ll sol = cifre.first;
	for (int i = 1; i < (1 << t); i++) {
		ll nr = 0, prod = 1;
		for (int j = 1; j < t; j++)
			if ((1 << j) & i) {
				prod = 1LL * prod * fact[j + 1];
				nr++;

			}

		if (nr % 2) nr = -1;
		else nr = 1;

		sol = sol + 1LL * nr * cifre.first / prod;
	}

	o << sol / 2 << "\n";

}

int main() {
	f >> m;
	erathosthene();
	while (m--) {
		//d = 1;
		f >> cifre.first >> cifre.second;
		cate();



	}





	return 0;
}