#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <fstream>
#include <map>
using namespace std;
#define MAX 1000001

bool p[MAX];
vector<long long>pr;
int k, f[20], x[20];

void ciur() {
	int i = 2;
	while (i <= 1000) {
		while (p[i])i++;
		for (int j = i*i; j < MAX; j += i) p[j] = 1;
		i++;
	}
	for (int i = 2; i < MAX; i++)
		if (!p[i]) pr.push_back(i);
}

void desc(long long n) {
	int i = 0;
	k = 0;
	while (i < pr.size() && pr[i] * pr[i] <= n) {
		if (n % pr[i] == 0) {
			k++;
			f[k] = pr[i];
			while (n % pr[i] == 0) {
				n /= pr[i];
			}
		}
		i++;
	}
	if (n != 1) {
		k++;
		f[k] = n;
	}
}

void solve(long long n) {
	long long sol = 0, p = 1;
	int i, nr = 0;
	memset(x, 0, sizeof(x));
	while (x[k+1] == 0) {
		i = 1;
		while (x[i]) {
			x[i] = 0;
			p /= f[i];
			i++;
			nr--;
		}
		p *= f[i];
		x[i] = 1;
		nr++;
		if (x[k+1] == 0) {
			if (nr % 2) {
				sol += n / p;
			} else {
				sol -= n / p;
			}
		}
	}
	cout << n - sol << "\n";
}

int t;

int main() {
	long long a, b;
	
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
		
	ciur();
	
	cin >> t;

	while(t--) {
		cin >> a >> b;
		desc(b);
		solve(a);
	}
	
	return 0;
}