#include<bits/stdc++.h> #define ing long long #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); } int n; bool flag[2010]; int check(int n,int k){ int g=__gcd(n,k); int ans=0; int cnt=0,i=k-1; while(cnt<n/g){ int tcnt=(n-i-1)/k+1; int l=1,r=tcnt+1; while(l<r){ int mid=(l+r)/2; if(i+(mid-1)*k>=cnt+mid) r=mid; else l=mid+1; } if(l<=tcnt){ int st=i+(l-1)*k,ed=i+(tcnt-1)*k; ans+=1LL*(st+ed)*(tcnt-l+1)/2+(tcnt-l+1); } cnt+=tcnt; i=(i+(tcnt-1)*k+k)%n; } return ans; } signed main(){ //txt_r(); int t; cin>>t; while(t--){ int n,m; 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{ int ans=-1; int k=0; for(int i=1;i<=min(n,m);i++){ int num=check(n,i); if(num>ans)ans=num,k=i; } cout<<k<<endl; } } return 0; }