// 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;
}

namespace out{
    char buffer[1<<21];int p1=-1;const int p2 = (1<<21)-1;
    inline void flush(){fwrite(buffer,1,p1+1,stdout),p1=-1;}
    inline void putc(const char &x) {if(p1==p2)flush();buffer[++p1]=x;}
    template <typename T>void write(T x) {
        static char buf[15];static int len=-1;if(x>=0){do{buf[++len]=x%10+48,x/=10;}while (x);}else{putc('-');do {buf[++len]=-(x%10)+48,x/=10;}while(x);}
        while (len>=0)putc(buf[len]),--len;
    }
}

#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 4000015
#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+2000003,*sa=SA+2000003;
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;
	n=min(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;
	
	res-=t*(t+1);
	//For(d,1,t) res-=d*2;
	
	
//	cout<<"RES "<<res<<"\n";
//	For(d,1,t){
//	//	res-=d*2;
//		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]);
//	//			cout<<"Sub "<<now<<"\n";
//				res-=now;
//			}
//		}
//	}

	auto pres=[&](int l,int r){
		assert(r<=n);
		assert(l>=-n);
		return sa[r]-sa[l-1];
	};
	res-=t;
//	cerr<<"Res "<<res<<"\n";
	
	For(i,-2*t,-1){
		int j=(-i+1)/2;
//		cout<<"i,j "<<i<<" "<<j<<"\n";
		res-=a[i]*pres(i+j,i+t);
	}
	For(i,1,t){
		res-=a[i]*pres(i+i,i+t);
	}
//	cout<<"qwq "<<res<<"\n";
	For(i,0,t-1)
		res-=a[i-t]*pres(0,i);
//	cout<<"qwq2 "<<res<<"\n";
	
	sa[-n-1]=sa[-n-2]=0;
	For(i,-n,n){
		sa[i]=a[i];
		if(i-2>=-n) sa[i]+=sa[i-2];
	}
	For(i,-2*t,-1){
		int j=(-i+1)/2;
//		cout<<"i,j "<<i<<" "<<j<<" "<<a[i]<<" "<<sa[i+2*t]<<" "<<sa[i+2*(j-1)]<<"\n";
		res-=a[i]*(sa[i+2*t]-sa[i+2*(j-1)]);
	//	cout<<"ovo "<<a[i]*(sa[i+2*t]-sa[i+2*(j-1)])<<"\n";
		//cout<<"res: "<<res<<"\n";
	}
	
//	cerr<<"res "<<res<<"\n";
	res/=4;
//	cout<<res<<"\n";
//	printf("%lld\n",res);
	out::write(res),out::putc('\n');
}

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