#include<bits/stdc++.h>
using namespace std;

void solve(){
  using ll=long long;
  ll n,k;
  cin>>n>>k;
  auto check=[&](ll x){
    for (ll i=1;i*i<=x&&i<=k;i++){
      if (x%i==0&&x/i<=k) return false;
    }
    return true;
  };
  for (ll x=n;x>=k;x--){
    if (check(x)){
      cout<<x<<endl;
      return;
    }
  }
  cout<<-1<<endl;
}

int main(){
  int t;
  cin>>t;
  while (t--) solve();
}