#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() { // freopen("number.in", "r", stdin); // freopen("number.out", "w", stdout); 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); } // cout << clock() / 1000.0 << endl; return 0; }