#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,
				 std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag,
				 __gnu_pbds::tree_order_statistics_node_update>
	trr;
using namespace __gnu_cxx;
//*/
#define ll long long
#define pi pair<ll, ll>
#define fi first
#define se second
ll t, a, m, ans, g, val[111], f[11111], cnt;
ll gcd(ll x, ll y)
{
	// cerr << x << " " << y << "\n";
	if (!y)
		return (x == 1);
	if ((!(x & 1ll)) && (!(y & 1ll)))
		return 0;
	while (!(x & 1ll))
		x >>= 1;
	while (!(y & 1ll))
		y >>= 1;
	if (x < y)
		swap(x, y);
	return gcd(y, x - y);
}
void solve1()
{
	for (ll i = a; i < a + m; i++)
	{
		if (i % g != 0)
			continue;
		ans += (gcd(i / g, m / g));
	}
	printf("%lld\n", ans);
}
void fun(ll x)
{
	for (ll i = 2; i <= x / i; i++)
		if (x % i == 0)
		{
			val[cnt++] = i;
			while (x % i == 0)
				x /= i;
		}
	if (x > 1)
	{
		val[cnt++] = x;
	}
}
void dfs(ll v, ll pos, ll x)
{
	if (pos == cnt){
		ans += x * (m / v);
		return;
	}
	dfs(v, pos + 1, x);
	dfs(v * val[pos], pos + 1, -x);
}
void solve()
{
	cnt = 0;
	a /= g;
	m /= g;
	fun(m);
	// cerr << m << "\n";
	dfs(1, 0, 1);
	printf("%lld\n", ans);
}
int main()
{
	scanf("%lld", &t);
	while (t--)
	{
		scanf("%lld%lld", &a, &m);
		g = __gcd(a, m);
		ans = 0;
		if (m <= 100000)
		{
			solve1();
		}
		else
		{
			solve();
		}
	}
	return 0;
}