#include "bits/stdc++.h"
#define DEBUG_OFF
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define range basic_string_view
using namespace std; typedef long long ll; constexpr __int128_t I=1;
void solve(){
    ll p; int t; cin>>p>>t; if(p-1<t+t) return cout<<0<<'\n',void();
    auto qpow=[&](ll x,ll y){
        ll res=1; while(y) { if(y&1) res=I*res*x%p;; x=I*x*x%p; y>>=1; }; return res;
    };
    auto test=[&](ll x) { return x%p==0?0:qpow(x%p,(p-1)/2)==1?1:-1; };
    ll ans=t*(p-3)+1;
    vector<int> suf(t*2+1),pre(t*2+1); For(i,1,t*2) pre[i]=pre[i-1]+test(i),suf[i]=suf[i-1]+test(p-i);
    for(int i=t*2,s0=0,s1=0;i>=0;i--){
        swap(s0,s1); s0+=suf[t*2-i]-(i==t*2?0:suf[t*2-i-1]);
        ans-=(pre[i]-(i==0?0:pre[i-1]))*s0+(t*2-i)/2+1; debug(i,ans);
    }
    // For(i,1,t) ans-=test(i)*test(p-i)+1;; debug(ans);
    For(i,1,t){
        ans-=(pre[i]-pre[i-1])*(suf[t-i]+pre[i+t]-pre[i*2-1]);
        ans-=(suf[i]-suf[i-1])*(pre[t-i]+suf[i+t]-suf[i*2-1]);
    }
    debug(ans); assert(ans%4==0); cout<<ans/4<<'\n';
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    int T; cin>>T; while(T--) solve();
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: October 16 Mon, 22 : 48 : 42