#include <bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define int long long 

using namespace std;

int qp(int x, int k, int mod)
{
	int ans = 1;
	while(k)
	{
		if(k & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return ans % mod;
}

void solve()
{
	int a, p, ans = 0;
	std::cin >> a >> p;
	if(a & 1)
	{
		std::cout << "1\n";
		return;
	}
	int m = (1ll << p);
	for(int x = 1; x < p; x++)
		if(qp(a, x, m) == qp(x, a, m))
			ans++;
	int q1 = (p + a - 1) / a;
	ans += (1ll << (p - q1));
	q1 = 1ll << q1;
	ans -= p / q1;
	std::cout << ans + 1 << endl;
}

signed main()
{
	#ifdef ONLINE_JUDGE
	ioclear;
	#endif
	int t;
	std::cin >> t;
	while(t--)
		solve();
}