#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair const int maxn=1e7+10; int p,r; int T; int cnt[1010][10010]; struct Solsp { int qp[1010],qr[1010]; int cnt[1000010]; void sol() { for(int i=1;i<=T;i++) cin>>qp[i]>>qr[i]; for(int i=1;i<=T;i++) { int ans=0; for(int j=0;j<qp[i];j++) { cnt[j*j%qp[i]]++; } for(int j=0;j<qp[i];j++) { int rst=(qr[i]-(j*j)%qp[i]+qp[i])%qp[i]; if(rst!=j) ans+=cnt[rst]; else ans+=cnt[rst]*(cnt[rst]-1)/2; } cout<<ans<<endl; } } }tsp; struct Sol_2e5 { int qp[100010],qr[100010]; int cnt[1000010]; vector<pii> vec[100010]; int ans[100010]; void sol() { int mx=0; for(int i=1;i<=T;i++) cin>>qp[i]>>qr[i],vec[qp[i]].push_back(mp(qr[i],i)),mx=max(mx,qp[i]); for(register int i=1;i<=mx;i++) { for(register int j=0;j<i;j++) cnt[j]=0; for(register int j=0;j<i;j++) { cnt[j*j%i]++; } for(register int j=0;j<i;j++) for(pii t:vec[i]) { int rst=(t.fi-(j*j)%i+i)%i; if(rst!=j) ans[t.se]+=cnt[rst]; else ans[t.se]+=cnt[rst]*(cnt[rst]-1)/2; } } for(int i=1;i<=T;i++) cout<<ans[i]<<endl; } }t; signed main() { // freopen("cover.in","r",stdin); // freopen("cover.out","w",stdout); ios::sync_with_stdio(false); cin>>T; if(T<=1e3) { tsp.sol(); return 0; } t.sol(); return 0; }