Polycarp wants to buy exactly n shovels. The shop sells packages with shovels. The store has k types of packages: the package of the i-th type consists of exactly i shovels (1 ≤ i ≤ k). The store has an infinite number of packages of each type.

Polycarp wants to choose one type of packages and then buy several (one or more) packages of this type. What is the smallest number of packages Polycarp will have to buy to get exactly n shovels?

For example, if n=8 and k=7, then Polycarp will buy 2 packages of 4 shovels.

Help Polycarp find the minimum number of packages that he needs to buy, given that he: 

  * will buy exactly n shovels in total; 
  * the sizes of all packages he will buy are all the same and the number of shovels in each package is an integer from 1 to k, inclusive. 

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases in the input. Then, t test cases follow, one per line.

Each test case consists of two positive integers n (1 ≤ n ≤ 10^9) and k (1 ≤ k ≤ 10^9) — the number of shovels and the number of types of packages.

Output

Print t answers to the test cases. Each answer is a positive integer — the minimum number of packages.

Example

Input


5
8 7
8 1
6 10
999999733 999999732
999999733 999999733


Output


2
8
1
999999733
1

Note

The answer to the first test case was explained in the statement.

In the second test case, there is only one way to buy 8 shovels — 8 packages of one shovel.

In the third test case, you need to buy a 1 package of 6 shovels.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
void io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin.tie(0);
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long div(long long a, long long b, long long m) {
  if (a % m == 0)
    return ((b / m) - (a / m) + 1);
  else
    return ((b / m) - (a / m));
}
struct dsu {
  vector<long long> par;
  dsu(long long n) {
    par.resize(n + 1);
    iota(par.begin(), par.end(), 0);
  }
  long long get(long long x) {
    if (par[x] == x) return par[x];
    par[x] = get(par[x]);
    return par[x];
  }
  void unite(long long x, long long y) {
    x = get(x);
    y = get(y);
    par[x] = par[y];
  }
};
void SieveOfEratosthenes(vector<long long> &a) {
  bool prime[1005];
  memset(prime, true, sizeof(prime));
  for (long long p = 2; p * p < 1005; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i < 1005; i += p) prime[i] = false;
    }
  }
  for (long long p = 2; p < 1005; p++) {
    if (prime[p]) a[p] = p;
  }
}
bool cmp(pair<long long, pair<long long, long long>> a,
         pair<long long, pair<long long, long long>> b) {
  if (a.second.second == b.second.second) {
    if (a.second.first == b.second.first) {
      return a.first < b.first;
    } else
      return a.second.first < b.second.first;
  } else
    return a.second.second < b.second.second;
}
const long long N = 1e5;
vector<long long> gr[N];
long long vis[N + 1];
void bfs_tree(long long source) {
  queue<long long> Q;
  Q.push(source);
  vis[source] = 1;
  while (!Q.empty()) {
    long long cur = Q.front();
    Q.pop();
    cout << cur << " ";
    for (auto x : gr[cur]) {
      if (!vis[x]) {
        vis[x] = 1;
        Q.push(x);
      }
    }
  }
}
void dfsGraph(long long curr) {
  cout << curr << "->";
  vis[curr] = 1;
  for (auto x : gr[curr]) {
    if (!vis[x]) dfsGraph(x);
  }
  return;
}
void dfsGraphWithoutVistedArray(long long curr, long long par) {
  cout << curr << "->";
  for (auto x : gr[curr]) {
    if (x != par) dfsGraphWithoutVistedArray(x, curr);
  }
  return;
}
long long checkPrime(long long n) {
  long long flag = 0;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      flag = 1;
      break;
    }
  }
  if (flag == 1)
    return 0;
  else
    return 1;
}
long long mo = 998244353;
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long mul_mod(long long a, long long b) {
  return ((a % mo) * (b % mo)) % mo;
}
long long add_mod(long long a, long long b) {
  return ((a % mo) + (b % mo)) % mo;
}
long long diff_mod(long long a, long long b) {
  return ((a % mo) - (b % mo)) % mo;
}
long long mod_inv(long long a, long long m) {
  long long val = binpow(a, m - 2, m);
  return val;
}
const long long NN = 500005;
long long fact[NN];
long long inver[NN];
void precompute() {
  fact[0] = 1;
  inver[0] = 1;
  long long pro = 1;
  for (long long i = 1; i < NN; i++) {
    pro = mul_mod(i, pro);
    fact[i] = pro;
    inver[i] = mod_inv(fact[i], mo);
  }
}
long long nck(long long n, long long k) {
  if (k > n or k < 0) return 0;
  long long ans = fact[n];
  ans = mul_mod(ans, inver[n - k]);
  ans = mul_mod(ans, inver[k]);
  return ans;
}
long long solve() {
  long long n, k, x, y;
  cin >> n >> k;
  vector<pair<long long, long long>> v;
  for (long long i = 0; i < n; i++) {
    cin >> x >> y;
    v.push_back({x, y});
  }
  precompute();
  sort(v.begin(), v.end());
  multiset<long long> ms;
  long long ans = 0;
  for (long long i = 0; i < n; i++) {
    while (!ms.empty() and (*ms.begin() < v[i].first)) ms.erase(ms.begin());
    long long cal_comb = nck(ms.size(), k - 1);
    ans = add_mod(cal_comb, ans);
    ms.insert(v[i].second);
  }
  cout << ans << "\n";
}
void suffix_sum(long long suffix[], long long a[], long long m) {
  suffix[m - 1] = a[m - 1];
  for (long long i = m - 2; i >= 0; i--) suffix[i] = a[i] + suffix[i + 1];
}
void pre_sum(long long pre[], long long a[], long long m) {
  pre[0] = a[0];
  for (long long i = 1; i, m; i++) pre[i] = a[i] + pre[i - 1];
}
int32_t main() {
  io();
  cout << fixed;
  cout.precision(10);
  long long t;
  cin >> t;
  while (t--) {
    long long n, m, k, x, y, z, l, r, q, num;
    string s;
    long long sum = 0;
    long long small = 0;
    cin >> n >> k;
    if (n <= k)
      cout << 1 << "\n";
    else {
      long long ans = INT_MIN;
      for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
          if (i <= k) ans = max(i, ans);
          if (n / i <= k) ans = max(ans, n / i);
        }
      }
      cout << n / ans << "\n";
    }
  }
  return 0;
}
