#include <bits/stdc++.h>
using namespace std;
#define int long long

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int mod = (int)1e9+7;//change this if needed
int modpow(int x, int y) {
	return !y?1:((y % 2 ? x : 1) * modpow((x * x) % mod, y / 2)) % mod;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		int a,p;
		cin >> a >> p;
		mod = 1<<p;
		if(a%2 == 1){
			cout << "1\n";
			continue;
		}
		if(a<=p){
			int k = (p+a-1)/a;
			int v = 1<<(p-k);
			for(int j = 1; j<=p; j++){
				if(j%(1<<k) == 0){
					if(modpow(a,j) != modpow(j,a)){
						v--;
					}
				}
				else{
					if(modpow(a,j) == modpow(j,a)){
						v++;
					}
				}
			}
			cout << v << '\n';
		}
		else{
			int v = 1<<(p-1);
			for(int j = 2; j<=p; j+=2){
				if(modpow(a,j) != modpow(j,a)){
					v--;
				}
			}
			for(int j = 1; j<=p; j+=2){
				if(modpow(a,j) == modpow(j,a)){
					v++;
				}
			}
			cout << v << '\n';
		}
	}
	return 0;
}