// 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;
	For(i,1,t)res+=p-2*i-4;
	
	int V=t*2-1;
	Rep(i,V,-V){
		if(i<=0)a[i]=(p%4==3?-a[-i]:a[-i]);
		else a[i]=(qpow(i,(p-1)/2)==1)?1:-1;
	}
	a[-V-1]=sa[-V-1]=0;
	For(i,-V,V)sa[i]=sa[i-1]+a[i];
	
	cout<<res<<"\n";
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/

answer.code:43:25: error: invalid conversion from ‘long long int*’ to ‘long long int’ [-fpermissive]
   43 | int A[maxn],SA[maxn],a=A+1000002,sa=SA+1000002;
      |                        ~^~~~~~~~
      |                         |
      |                         long long int*
answer.code:43:39: error: invalid conversion from ‘long long int*’ to ‘long long int’ [-fpermissive]
   43 | int A[maxn],SA[maxn],a=A+1000002,sa=SA+1000002;
      |                                     ~~^~~~~~~~
      |                                       |
      |                                       long long int*
answer.code: In function ‘void work()’:
answer.code:52:26: error: invalid types ‘long long int[long long int]’ for array subscript
   52 |                 if(i<=0)a[i]=(p%4==3?-a[-i]:a[-i]);
      |                          ^
answer.code:52:40: error: invalid types ‘long long int[long long int]’ for array subscript
   52 |                 if(i<=0)a[i]=(p%4==3?-a[-i]:a[-i]);
      |                                        ^
answer.code:52:46: error: invalid types ‘long long int[long long int]’ for array subscript
   52 |                 if(i<=0)a[i]=(p%4==3?-a[-i]:a[-i]);
      |                                              ^
answer.code:53:23: error: invalid types ‘long long int[long long int]’ for array subscript
   53 |                 else a[i]=(qpow(i,(p-1)/2)==1)?1:-1;
      |                       ^
answer.code:55:10: error: invalid types ‘long long int[long long int]’ for array subscript
   55 |         a[-V-1]=sa[-V-1]=0;
      |          ^
answer.code:55:19: error: invalid types ‘long long int[long long int]’ for array subscript
   55 |         a[-V-1]=sa[-V-1]=0;
      |                   ^
answer.code:56:22: error: invalid types ‘long long int[long long int]’ for array subscript
   56 |         For(i,-V,V)sa[i]=sa[i-1]+a[i];
      |                      ^
answer.code:56:28: error: invalid types ‘long long int[long long int]’ for array subscript
   56 |         For(i,-V,V)sa[i]=sa[i-1]+a[i];
      |                            ^
answer.code:56:35: error: invalid types ‘long long int[long long int]’ for array subscript
   56 |         For(i,-V,V)sa[i]=sa[i-1]+a[i];
      |                                   ^