// Problem: D. 去发现新的最小公约吧
// Contest: undefined - NOIP2024训练赛 10
// URL: http://www.noi.ac/contest/1162/problem/2809
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e5 + 10, M = 1e5 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans;
int s[N], dp[N], p[N], cnt;
bool vis[N];

vector<int> v;

inline void init()
{
	for(int i = 2; i <= M; i ++)
	{
		if(!vis[i]) p[++ cnt] = i;
		for(int j = 1; i * p[j] <= M && j <= cnt; j ++)
		{
			vis[i * p[j]] = true;
			if(i % p[j] == 0) break;
		}
	}
}

inline void getv(int x)
{
	v.clear();
	for(int i = 1; i <= cnt && x > 1; i ++)
	{
		if(x % p[i]) continue;
		int sum = 0;
		while(x % p[i] == 0) x /= p[i], sum ++;
		v.push_back(p[i]);
	}
	if(x > 1) v.push_back(x);
	// cout << "m = " << m << '\n';
	// for(auto i : v) cout << i << ' ';
	// cout << '\n';
}

inline int solve(int r)
{
	int res = 0;
	for(int st = 1; st < (1 << v.size()); st ++)
	{
		int mul = 1, flag = 0;
		for(int i = 0; i < v.size(); i ++)
			if((st >> i) & 1) flag ++, mul *= v[i];
		int now = r / mul;
		res += (flag % 2 ? now : -now);
	}
	// cout << "r = " << r << " ans = " << r - res << '\n';
	return r - res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	init();
	int T; cin >> T;
	while(T --)
	{
		cin >> n >> m; v.clear();
		int now = __gcd(n, m); 
		n /= now, m /= now; getv(m);
		// cout << m / (now - 1) << '\n';
		// cout << solve(m, m) - solve(n - 1, m) << '\n';
		// if(m > n) cout << solve(m) << '\n';
		// else cout << solve(n + m) - solve(n - 1) - 1 << '\n';
		cout << solve(n + m - 1) - solve(n - 1) << '\n';
	}
	return 0;
}