#include<bits/stdc++.h> using namespace std; typedef long long ll; int T; ll N, P; ll read(){ ll x(0); char c(getchar()); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } void write(ll x){ if(x >= 10)write(x / 10); putchar((x % 10) | 48); } ll gcd(ll a, ll b){ while(b){ int t(b); b = a % b; a = t; } return a; } void exgcd(ll a, ll b, ll &x, ll &y){ if(!b)x = 1, y = 0; else exgcd(b, a % b, y, x), y -= a / b * x; } int main() { T = read(); while(T--){ N = read(); P = read(); ll S(N * (N - 1) / 2 % P); ll G(gcd(N, P)); if(S % G){ puts("-1"); continue; } S /= G; N /= G; P /= G; N = (P - N % P) % P; ll a(0), l(0); exgcd(P, N, a, l); l = (l % P + P) % P; l = l * S % P; write((l + P - 1) % P + 1); putchar(10); } return 0; }