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

#define rep(i, a, b) for (int i = a; i < b; i++)
using ll = long long;

int main(){
	int t;
	cin >> t;
	rep(ti, 0, t) {
		int n, k, ex = 0;
		cin >> n >> k;
		for(int x = n; x > k; x--) {
			int f = 0;
			for(ll a = 1; a * a <= x && a <= k; a++) {
				if(x % a) continue;
				int b = n / a;
				if(b <= k) {
					f = 1;
					continue;
				}
			}
			if(f == 0) {
				cout << x << endl;
				ex = 1;
				break;
			}
		}
		if(ex == 0) cout << -1 << endl;
	}
}