#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(Int x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=x*ans%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
ll mod;
ll Ler(ll x,ll mod){
	ll p=Math::QP(x,(mod-1)/2,mod);
	return p<=1?p:-1;
}
void solve(){
	//don't forget to open long long
	ll t;std::cin>>mod>>t;t=std::min(1ll*t,(mod-1)/2);
	ll S=0;
	ve<int>val(4*t+1);
	for(int i=0;i<=t*4;i++)
		val[i]=Ler(i+mod-2*t,mod);
//	for(int i=0;i<=t*4;i++)
//		std::cout<<val[i]<<' ';std::cout<<'\n';
	ve<int>S1(4*t+1),S2(4*t+1);
	for(int i=0;i<=t*4;i++){
		S1[i]=val[i];S2[i]=val[i];
		if(i)S1[i]+=S1[i-1];
		if(i>1)S2[i]+=S2[i-2];
	}ll ans=0; 
	for(int i=1;i<=t;i++)
		ans+=mod-4-Ler(i,mod)*Ler(i*2,mod);
	/*for(int i=1;i<=(mod-1)/2;i++){
		int res=0;
		for(int j=0;j<mod;j++)
			res+=1+Ler(j,mod)*Ler(j-i,mod)+Ler(j,mod)*Ler(j+i,mod)+Ler(j-i,mod)*Ler(j+i,mod);
		std::cerr<<res<<'\n';
	}*/
	for(int i=0;i<t*2;i++){
		ll L=(t*2-i+1)/2;
		ans-=(t-L+1)+val[i]*(S1[i+t]-S1[i+L-1]+S2[i+t*2]-S2[i+(L-1)*2]); 
	}
	for(int i=0;i<t*4;i++){
		ll L=std::max({i-t*2+1,t*2-i,1ll});
		ll R=std::min({t*4-1-i,t,1ll*i});
		if(L<=R)ans-=val[i]*(S1[i+R]-S1[i+L-1]);
	}
//	ans-=3*t+2*Ler(2,mod)*t+Ler(-1,mod)*t; 
	std::cout<<ans/4<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	std::cin>>T;
	while(T--)solve();

	return 0;
}