#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll; inline ll Read() { static ll x=0,c=getchar(); for(; c<=47||c>=58; c=getchar()); for(x=0; c>=48&&c<=57; c=getchar()) x=(x<<3)+(x<<1)+(c&15); return x; } int main() { // freopen("number.in","r",stdin); // freopen("number.out","w",stdout); ll t=Read(); while(t--) { ll n=Read(),p=Read(),x=0; for(ll i=1; i<=n-1; i++) x=(x+i)%p; int m=(p-x)%p; bool f=0; for(ll i=1; i<=p; i++) if(((n%p)*i)%p==m) { printf("%lld\n", i); f=1; break; } if(!f) printf("-1\n"); } return 0; }