#include<bits/stdc++.h> using namespace std; template<typename T>void in(T &a) { T ans=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())ans=ans*10+c-'0'; a=ans; } template<typename T,typename... Args>void in(T &a,Args&...args) { in(a),in(args...); } template<typename T>inline T gcd(T m,T n){ return n?gcd(n,m%n):m; } void exgcd(long long a,long long b,long long &x,long long &y){ if(!b){ x=1,y=0; return; } exgcd(b,a%b,y,x),y-=a/b*x; } long long solve(long long n,long long p){ long long c=((n-n*n)%(2*p)+2*p)%(2*p),d=gcd(2*n,2*p); if(c%d)return -1; long long x,y; exgcd(2*n,2*p,x,y); x*=(c/d); return (x%((2*p)/d)+((2*p)/d))%((2*p)/d); } int t; long long n,p; int main(){ in(t); while(t--)in(n,p),printf("%lld\n",solve(n,p)); return 0; }