#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;

struct DIV {
	u64 x;
	void init(u64 v) { x = -1ull / v + 1; }
};
u64 operator / (const u64 & x, const DIV & y) {
	using u128 = __uint128_t;
	return y.x ? (u128) x * y.x >> 64 : x;
}
ll ipow(ll a, ll b) {
	ll ans = 1;
	for(;b;--b) ans *= a;
	return ans;
}
ll solve(int index, ll a, ll b) {
	if(index == cc) {
		ll sum = 0;
		if(a > b) {
			DIV B; B.init(b);
			for(int k1 = 0;k1 * a < 2 * n;++k1) {
				ll min = std::min(k1 * a, 2 * n - 1 - k1 * a);
				int p = k1 * a & 1;
				if((b & 1) == 0) {
					if(p == 0) sum += min / B;
				} else {
					sum += (min / B + p) >> 1;
				}
			}
		} else {
			DIV A; A.init(a);
			for(int k2 = 1;k2 * b < n;++k2) {
				ll lower = k2 * b - 1;
				ll upper = 2 * n - k2 * b - 1;
				int p = k2 * b & 1;
				if((a & 1) == 0) {
					if(p == 0) sum += upper / A - lower / A;
				} else {
					sum += (upper / A + p) >> 1;
					sum -= (lower / A + p) >> 1;
				}
			}
		}
		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();
	}
}