#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1; char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x*f; } int t,n,p,ans=-1; signed main(){ t=read(); while(t--){ n=read(),p=read(); 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("%lld\n",ans); } return 0; }