#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
using big=__int128;
const int N=2e6+10;
ll p;
int T,n,t;
ll qpow(big x,ll y,ll mod){
	big ans=1;
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
bool chk(ll x,ll p){
	return qpow(x,(p-1)/2,p)==1;
}
int a[N],b[N],c[N*2],s[N*2];
ll calc(ll p){
	int cnt=chk(p-2,p)==chk(p-1,p)&&!chk(p-1,p);
	if(p%4==3)return p/4-cnt;
	else if(p%8==5)return p/4-1-cnt;
	else return p/4-2-cnt;
}
ll solve(int *a,int n){
	// ll sum=0;
	// for(int i=0;i<n;i++){
	// 	for(int t=1;i-t>=0&&i+t<n;t++){
	// 		sum+=a[i]*a[i-t]+a[i]*a[i+t]+a[i-t]*a[i+t]+1;
	// 	}
	// }
	// debug(ary(a,0,n-1),sum);
	// return sum;
	for(int i=0;i<n;i++){
		s[i]=(i?s[i-1]:0)+a[i];
	}
	auto calc=[&](int l,int r){
		if(l-->r)return 0;
		return (r>=0?s[r]:0)-(l>=0?s[l]:0);
	};
	ll ans=0;
	for(int i=0;i<n;i++){
		int x=min({t,i,n-i-1});
		ans+=a[i]*(calc(i-x,i-1)+calc(i+1,i+x));
	}
	// debug(ans);
	for(int i=0,x=0;i<n;i+=2){
		ans+=a[i]*x,x+=a[i];
		if(i>=t+t)x-=a[i-t-t];
	}
	for(int i=1,x=0;i<n;i+=2){
		ans+=a[i]*x,x+=a[i];
		if(i>=t+t)x-=a[i-t-t];
	}
	// debug(ans);
	for(int i=1;i<=t;i++){
		ans+=max(0,n-(i*2+1)+1);
	}
	// debug(ary(a,0,n-1),ans);
	return ans;
}
void get(){
	scanf("%lld%d",&p,&t);
	n=min(p-1,2ll*t);
	ll res=1ll*t*calc(p),ans=0;
	for(int i=1;i<=n;i++)a[i]=chk(i,p)?1:-1;
	for(int i=1;i<=n;i++)b[i]=chk(p-i,p)?1:-1;
	for(int i=1;i<=n;i++)c[n-i+1]=b[i];
	c[n+1]=0;
	for(int i=1;i<=n;i++)c[n+1+i]=a[i];
	ans=solve(c+1,n*2+1)-solve(a,n+1)-solve(b,n+1);
	for(int i=1;i<=n&&i<=t;i++){
		ans-=a[i]*b[i]+1;
	}
	// debug(res,ans);
	printf("%lld\n",res-ans/4);
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}