#define ll long long
#define fr first
#define sc second
#define pb(x) push_back(x)
#define nxt continue
#define sz(container) ((ll) container.size())
#define umap unordered_map
#define uset unordered_set
#define MAX LONG_LONG_MAX
#define MIN LONG_LONG_MIN
#define mkpr(f, s) make_pair(f, s)
#define el '\n'

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

const ll MOD = 1e9;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
  
  ll t, n, a, i;
  
  cin >> t;
  
  while (t--) {
    cin >> n >> a;
    
    for (i = n; i > a; --i)
      if (__gcd(i, a) == 1)
        break;
        
    cout << i << el;
  }
  
	return 0;
}