#include "bits/stdc++.h"

using namespace std;
using int64 = int64_t;
using int128 = __int128_t;

const int ITERS = 100;

void solve() {
  int64 n, a;
  cin >> n >> a;
  optional<pair<int128, int64>> ans;
  bool foundCoPrime = false;
  for (int i = 0; i < ITERS && n > 0; ++i) {
    int64 gcd = std::gcd(n, a);
    if (gcd == 1) {
      foundCoPrime = true;
    }
    int128 res = (int128)a * n / gcd / gcd;
    if (!ans.has_value() || res >= ans.value().first) {
      ans = make_pair(res, n);
    }
    --n;
  }
  assert(foundCoPrime);
  cout << ans.value().second << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}