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

long long pg(ll a,ll b,ll mod)
{
	ll temp=a,ans=1;
	while(b!=0)
	{
		if(b&1)
        ans=(ans*temp)%mod;
		temp=(temp*temp)%mod;
		b>>=1;
	}
	return ans;
}
//打表函数
void init()
{
	ll ans=0;
	ll mod=1<<20;
	for(int a=1;a<=50;a++)
	{
		for(int i=1;i<=20;i++)
		{
			if(pg(a,i,mod)%mod==pg(i,a,mod)%mod)
			{
				ans++;
			}
		}
		if(a&1)	cout<<"奇数"<<endl;
		cout<<ans<<endl;

		ans=0;
	}

}
int main()
{
//	init();
	ll t;
	cin>>t;
	while(t--)
	{
		ll a,p;
		cin>>a>>p;
		if(a&1)
		{
			cout<<"1"<<endl;
			continue;
		}
		else
		{
			ll ans=0;
			ll mod=1<<p;
			for(int i=1;i<=p;i++)
			{
				if(pg(a,i,mod)%mod==pg(i,a,mod)%mod)
				{
					ans++;
				}
			}
			ll q1;
				q1=p/a;
			if(p%a)
				q1++;
			ll l=1<<q1;
			ans+=(mod/l-p/l);
			cout<<ans<<endl;
		}

	}
	return 0;
}