#include <bits/stdc++.h> using namespace std; inline int read(){ int x=0;bool f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();} while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return f?x:-x; } int n,p,t,ans; int main(){ // freopen("number.in","r",stdin); // freopen("number.out","w",stdout); t=read(); while(t--){ n=read(),p=read(),ans=-1; if(p==1){ puts("1"); continue; } for(int i=1;i<=100;i++) if(!(((i<<1)+n-1)*n%(p<<1))){ ans=i; break; } printf("%d\n",ans); } return 0; }