#include<bits/stdc++.h>
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int N = 200;
int t, n, m;
int p[N], c[N], cc;

ll ans = 0;

ll ipow(ll a, ll b) {
	ll ans = 1;
	for(;b;--b) ans *= a;
	return ans;
}
u64 floor_sum(u64 n, u64 m, u64 a, u64 b) {
	u64 ans = 0;
	for(;;) {
		if(a >= m) ans += n * (n - 1) / 2 * (a / m), a %= m;
		if(b >= m) ans += n * (b / m), b %= m;
		u64 ymax = a * n + b; // use u128 if it's big
		if(ymax < m) break;
		n = ymax / m;
		b = ymax % m;
		std::swap(m, a);
	}
	return ans;
}

ll solve(int index, ll a, ll b) {
	if(index == cc) {
		ll sum = 0;
		if(b % 2 == 0 || a % 2 == 0) {
			if(a % 2) a += a;
			if(b % 2) b += b;
			ll l = 0, mid = (n - 1) / a, r = (2 * n - 1) / a;

			sum += floor_sum(mid + 1, b, a, 0);
			sum += floor_sum(r - mid, b, a, 2 * n - 1 - r * a);
		} else {
			ll l = 0, mid = (n - 1) / a, r = (2 * n - 1) / a;

			sum += floor_sum((mid + 1 + 1) / 2, b * 2, a * 2, 0);
			sum += floor_sum((mid + 1 + 0) / 2, b * 2, a * 2, b + a);

			int sgn = r & 1;
			sum += floor_sum((r - mid + !sgn) / 2, b * 2, a * 2, 2 * n - 1 - r * a + sgn * a);
			sum += floor_sum((r - mid + sgn) / 2, b * 2, a * 2, 2 * n - 1 - r * a + b + !sgn * a);
		}
		return sum;
	}

	ll ans = 0;
	for(int i = 0;i <= c[index];++i) {
		ans += solve(index + 1, a * ipow(p[index], i), b * ipow(p[index], c[index] - i));
	}
	for(int i = 1;i <= c[index];++i) {
		ans -= solve(index + 1, a * ipow(p[index], i), b * ipow(p[index], c[index] - i + 1));
	}
	return ans;
}

void solve() {
	cin >> n >> m, cc = 0;
	memset(c, 0, sizeof(c));
	int x = m;
	for(int i = 2;i * i <= x;++i) {
		if(x % i == 0) {
			p[cc] = i;
			while(x % i == 0) {
				++ c[cc];
				x /= i;
			}
			++ cc;
		}
	}
	if(x > 1) p[cc] = x, c[cc] = 1, ++ cc;
	ans = solve(0, 1, 1);
	cout << ans << '\n';
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> t;
	for(int i = 0;i < t;++i) {
		solve();
	}
}