#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define EFC cin.tie(nullptr)->ios_base::sync_with_stdio(false)
int d1[5] = { 0, -1, 0, 1, 0 };
int d2[5] = { 0, 0, 1, 0, -1 };
const int mod = 1e9 + 7;
int d11[9] = { 0 , -1, -1, 0, 1, 1, 1, 0, -1 };
int d22[9] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
int est[3] = { 0, -1, 0 };
int est1[3] = { 0, 0, 1 };
ifstream fin("pinex.in");
ofstream fout("pinex.out");

/*

  1 3 5 2 4
*/

//----------------------------------

int n;
int main() {

	fin >> n;
	while (n--) {
		unsigned long long a, b, d, p;
		fin >> a >> b;
		long double ans = a;
		
		d = 2;
		while (b > 1) {
			p = 0;
			while (b % d == 0) {
				b /= d, p++;
			}
			if (p) {
				double c = 1 - (1 / (d * 1.0));
				ans *= c;
			}
			d++;
			if (d * d > b && b > 1) {
				d = b;
			}
		}
		if (ans != (int)ans) ans++;
		fout << (int)ans << '\n';
	}
}