#include <bits/stdc++.h>

#define NMAX 200005
#define VALMAX 1000000
using namespace std;

typedef unsigned long long ull;

vector<int> prime, toIt;
bool ciur[VALMAX + 5];
ull dp[2][NMAX], st[2][NMAX], nr[3];
ull rez = 0;

void make_ciur(){
	for(ull i = 2; i <= VALMAX; ++i)
		if(ciur[i] == 0){
			prime.push_back(i);
			for(ull j = i * i; j <= VALMAX; j += i)
				ciur[j] = 1;
		}
}

void build(ull A, ull B){
	ull cB = B;
	for(int i = 0; i < prime.size() && prime[i] <= B; ++i)
		if(B % prime[i] == 0){
			dp[0][++nr[0]] = prime[i];
			st[0][nr[0]] = nr[0];
			rez += A / prime[i];
			toIt.push_back(prime[i]);
			while(cB % prime[i] == 0)
				cB /= prime[i];
		}
		else if(prime[i] > sqrt(cB) && cB != 1){
			dp[0][++nr[0]] = cB;
			st[0][nr[0]] = nr[0];
			rez += A / cB;
			toIt.push_back(cB);
			return;
		}
}

int main(){
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	int t;
	cin >> t;

	make_ciur();
	while(t--){
		ull A, B;
		cin >> A >> B;

		toIt.push_back(0);
		nr[0] = nr[1] = 0;
		rez = 0;
		build(A, B);

		int lim = nr[0];
		int curL = 1, lastL = 0;
		for(int pas = 2; pas <= lim; ++pas){
			for(int i = 1; i <= nr[lastL]; ++i)
				for(int j = st[lastL][i] + 1; j <= lim; ++j)
					if(dp[lastL][i] * toIt[j] <= A){
						dp[curL][++nr[curL]] = dp[lastL][i] * toIt[j];
						st[curL][nr[curL]] = j;

						if(pas % 2 == 0)
							rez -= A / dp[curL][nr[curL]];
						else rez += A / dp[curL][nr[curL]];
					}
					else break;
			nr[lastL] = 0;
			curL = 1 - curL;
			lastL = 1 - lastL;
		}

		cout << A - rez << '\n';
		toIt.clear();
	}
	return 0;
}