// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 2000005
#define inf 0x3f3f3f3f

ll p,res;
int t;
long double iP;
ll mul(ll x,ll y){
	ll d=x*iP*y+0.5,s=x*y-d*p;
	return s+((s>>63)&p);
}
ll qpow(ll a,ll b){
	ll c=1;
	for(;b;b>>=1,a=mul(a,a))if(b&1)c=mul(c,a);
	return c;
}

int A[maxn],SA[maxn],*a=A+1000002,*sa=SA+1000002;
void work()
{
	p=read(),t=read(),iP=1.0l/p;
	t=min(t,p/2-1),res=0;
	
	int n=t*2;
	n=p-1;
	Rep(i,n,-n){
		if(i<=0)a[i]=(p%4==3?-a[-i]:a[-i]);
		else a[i]=(qpow(i,(p-1)/2)==1)?1:-1;
	}
	a[-n-1]=sa[-n-1]=0;
	For(i,-n,n)sa[i]=sa[i-1]+a[i];
	
//	For(d,1,t){
//		int sum=0,sum2=0;
//		For(i,0,p-1){
//			int now=a[i]*a[(i+d)%p]+(a[(i+d)%p]*a[(i+d*2)%p])+(a[i]*a[(i+2*d)%p]);
//			now+=1;
////			cerr<<"now "<<now<<"\n";
//			sum+=a[i]*a[(i+d)%p],sum+=(a[(i+d)%p]*a[(i+d*2)%p]),sum2+=(a[i]*a[(i+2*d)%p]);
//		}
//	//	sum=sum*2+sum2;
//		sum+=sum2;
//		sum+=p;
//		cout<<sum<<"\n";
//	//	sum-=(a[d]*a[(p-d)%p]+1);
//	//	cout<<"S "<<sum<<"\n";
//		res+=sum;
//	}
	res+=(p-3)*t;
//	cout<<"RES "<<res<<"\n";
	For(d,1,t){
		For(i,0,p-1){
			if(i+d*2>=p){
				int now=a[i]*a[(i+d)%p]+(a[(i+d)%p]*a[(i+d*2)%p])+(a[i]*a[(i+2*d)%p]);
				now+=1;
	//			cout<<"Sub "<<now<<"\n";
				res-=now;
			}
		}
	}
	cerr<<"res "<<res<<"\n";
	res/=4;
	cout<<res<<"\n";
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*
7
7 32
13 1
13 2
67 11
2003 44
1000003 1984
999999999989 987654
*/