#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; int s=(1+n)*n/2; int k=s%m; bool flag=false; for(int i=1;i<=m;i++) { s+=2; if(s%m==k&&s%m!=0) { flag=true; break; } } if(flag==true) { cout<<"-1"<<endl; continue; } int l=0; while(1) { l++; if((n*(n-1+2*l)/2)%m==0) { cout<<l<<endl; break; } } } return 0; }