#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
void solve() {
  int a, b; cin >> a >> b;
  int sum = (a + a + b - 1) * b / 2;
  vector<int> factors;
  for (int i = 1; i * i <= sum; i++) {
    if (sum % i == 0) {
      factors.push_back(i);
      if (i * i != sum) factors.push_back(sum / i);
    }
  }
  sort(factors.rbegin(), factors.rend());
  int gcd = 1;
  vector<int> prefix_sum(b);
  prefix_sum[0] = a;
  for (int i = 1; i < b; i++) {
    prefix_sum[i] = prefix_sum[i - 1] + a + i;
  }
  int ans = 1;
  for (int i : factors) {
    int good = 0;
    for (int ss = 1; ss < b; ss++) {
      int lo = prefix_sum[ss - 1];
      int hi = prefix_sum[b - 1] - prefix_sum[b - 1 - ss];
      if (hi - lo >= i or hi % i <= lo % i) good = 1;
    }
    if (good) {cout << i << endl; return;}
  }
  cout << 1 << endl;
}

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