#include<bits/stdc++.h> #define pii pair<int,int> #define mkp make_pair using namespace std; void txt_r(){ freopen("test.in","r",stdin);freopen("test.out","w",stdout); //freopen("b.in","r",stdin);freopen("b.out","w",stdout); } bool flag[2010]; int n,m; __int128_t check(int k){ int g=__gcd(n,k); __int128_t ans=0; int cnt=0,i=k-1; while(cnt<n/g){ int cnt2=(n-i-1)/k+1; int l=1,r=cnt2+1; while(l<r){ int mid=(l+r)>>1; if(i+(mid-1)*k>=cnt+mid)r=mid; else l=mid+1; } if(l<=cnt2){ __int128_t st=i+(l-1)*k,ed=i+(cnt2-1)*k; ans+=(st+ed)*(cnt2-l+1)/2+(cnt2-l+1); } cnt+=cnt2; i=(i+(cnt2-1)*k+k)%n; } return ans; } signed main(){ //txt_r(); int t; cin>>t; while(t--){ cin>>n>>m; if(m==1||n==1)cout<<1<<endl; else if(n<=2000){ int ans=1,mx=0; for(int i=1;i<=m;i++){ int k=0; int sum=0; memset(flag,0,sizeof(flag)); for(int j=1;j<=n;j++){ flag[j]=1; k+=i; if(!flag[((k-1)%n)+1])flag[((k-1)%n)+1]=1,sum+=((k-1)%n)+1; } if(mx<sum){ mx=sum,ans=i; } } cout<<ans<<endl; }else{ __int128_t ans=-1; int k=0; for(int i=1;i<=min(n,m);i++){ __int128_t num=check(i); if(num>ans)ans=num,k=i; } cout<<k<<endl; } } return 0; }