#include <bits/stdc++.h>
const int64_t N_limit = 1000000000;
void calc_small_primes_needed(std::vector<int64_t> &ARR, int64_t max_n,
                              int64_t &result_tot_num) {
  int64_t ARR_size = 1 + ceil(max_n / (1 + floor(log(ceil(max_n / 10)))));
  ARR.resize(ARR_size);
  if (max_n < 1) {
    std::cerr << "Your n isn't natural integer" << std::endl;
    exit(1);
  }
  if (max_n == 1) {
    ARR[0] = 1;
    result_tot_num = 0;
    return;
  }
  if (max_n == 2) {
    ARR[0] = 1;
    ARR[1] = 2;
    result_tot_num = 1;
    return;
  }
  if (max_n == 3 || max_n == 4) {
    ARR[0] = 1;
    ARR[1] = 2;
    ARR[2] = 3;
    result_tot_num = 2;
    return;
  }
  ARR[0] = 1;
  ARR[1] = 2;
  ARR[2] = 3;
  int64_t total_primes = 2;
  int64_t tot_primes_runner = 2;
  int64_t div_edge = 0;
  int64_t curr_div = 3;
  for (int64_t ii = 5; ii <= max_n; ii += 2) {
    tot_primes_runner = 2;
    div_edge = 1 + floor(sqrt(ii));
    bool prime_indicator = true;
    curr_div = 3;
    while (curr_div < div_edge) {
      if (ii % curr_div == 0) {
        prime_indicator = false;
        break;
      } else {
        if (tot_primes_runner < total_primes) {
          ++tot_primes_runner;
          curr_div = ARR[tot_primes_runner];
        } else
          curr_div += 2;
      }
    }
    if (prime_indicator) {
      ++total_primes;
      ARR[total_primes] = ii;
    }
  }
  result_tot_num = total_primes;
}
void factor_decomposition(std::vector<int64_t> &pr_list,
                          std::vector<std::pair<int64_t, int64_t> > &decomp,
                          int64_t num, int64_t &tot_div) {
  if (num == 1) {
    decomp[0].first = 1;
    decomp[0].second = 1;
    tot_div = 0;
    return;
  }
  int64_t pr_list_index = 1;
  int64_t tot_pr_divs = 0;
  int64_t curr_div = pr_list[pr_list_index];
  bool indicator = false;
  int64_t sqrt_num = 1;
  while (num > 1) {
    sqrt_num = 1 + ceil(sqrt(num));
    curr_div = pr_list[pr_list_index];
    if (curr_div > sqrt_num) {
      ++tot_pr_divs;
      decomp[tot_pr_divs].first = num;
      ++decomp[tot_pr_divs].second;
      num = 1;
      break;
    }
    if (num % curr_div == 0) {
      num /= curr_div;
      if (indicator == false) {
        indicator = true;
        ++tot_pr_divs;
        decomp[tot_pr_divs].first = pr_list[pr_list_index];
        ++decomp[tot_pr_divs].second;
      } else
        ++decomp[tot_pr_divs].second;
    } else {
      if (indicator == true) {
        ++pr_list_index;
        indicator = false;
      } else
        ++pr_list_index;
    }
  }
  tot_div = tot_pr_divs;
}
void filling(std::vector<std::pair<int64_t, int64_t> > &powers, int64_t jj) {
  if (powers[jj].first < powers[jj].second) {
    ++powers[jj].first;
  } else {
    powers[jj].first = 0;
    ++jj;
    filling(powers, jj);
  }
}
void quickSort(std::vector<int64_t> &AR, int64_t low, int64_t high) {
  int64_t left_index = low;
  int64_t right_index = high;
  double pivot = AR[(left_index + right_index) / 2];
  double buffer = 0.0;
  while (left_index <= right_index) {
    while (AR[left_index] < pivot) left_index++;
    while (AR[right_index] > pivot) right_index--;
    if (left_index <= right_index) {
      buffer = AR[left_index];
      AR[left_index] = AR[right_index];
      AR[right_index] = buffer;
      left_index++;
      right_index--;
    }
  }
  if (right_index > low) quickSort(AR, low, right_index);
  if (left_index < high) quickSort(AR, left_index, high);
}
int main() {
  int64_t t;
  std::cin >> t;
  std::vector<int64_t> answer = {0};
  answer.resize(t + 1);
  std::vector<int64_t> small_primes = {0};
  int64_t highest_small_prime = 300 + round(sqrt(N_limit));
  int64_t tot_small_pr_num = 0;
  calc_small_primes_needed(small_primes, highest_small_prime, tot_small_pr_num);
  int64_t n = 0;
  int64_t k = 0;
  for (int64_t ii = 1; ii <= t; ii++) {
    std::cin >> n >> k;
    if (n <= k) {
      answer[ii] = 1;
      continue;
    }
    if (n == 1) {
      answer[ii] = 1;
      continue;
    }
    if (k == 1) {
      answer[ii] = n;
      continue;
    }
    std::vector<std::pair<int64_t, int64_t> > fact_decomp;
    fact_decomp.resize(50);
    int64_t tot_pr_dividers = 0;
    factor_decomposition(small_primes, fact_decomp, n, tot_pr_dividers);
    std::vector<std::pair<int64_t, int64_t> > powers;
    powers.resize(tot_pr_dividers + 1);
    int64_t tot_dividers = 1;
    for (int64_t kk = 1; kk <= tot_pr_dividers; kk++) {
      powers[kk].first = 0;
      powers[kk].second = fact_decomp[kk].second;
      tot_dividers *= (1 + fact_decomp[kk].second);
    }
    std::vector<int64_t> all_dividers = {0};
    all_dividers.resize(tot_dividers + 1);
    int64_t div = 1;
    int64_t div_counter = 1;
    all_dividers[div_counter] = div;
    while (div < n) {
      ++div_counter;
      filling(powers, 1);
      div = 1;
      for (int64_t bb = 1; bb <= tot_pr_dividers; bb++) {
        int64_t base_div = fact_decomp[bb].first;
        int64_t pow_div = powers[bb].first;
        div *= pow(base_div, pow_div);
      }
      all_dividers[div_counter] = div;
    }
    quickSort(all_dividers, 1, tot_dividers);
    div_counter = 1;
    while (all_dividers[div_counter] < k) ++div_counter;
    if (all_dividers[div_counter] == k)
      answer[ii] = n / all_dividers[div_counter];
    else
      answer[ii] = n / all_dividers[div_counter - 1];
  }
  for (int64_t ii = 1; ii <= t; ii++) std::cout << answer[ii] << std::endl;
  return 0;
}
