这是一道简单题。

我们不妨设 $n = 1$，因为这样可以让 $b$ 尽量大，从而找出一个合法的解。

那么问题转换为：是否存在一个 $m$ 满足 $c = \lfloor \frac{a}{m} \rfloor$。

我们可以采用二分查找的方法，在 $(\lfloor \frac{a}{c + 1} \rfloor, \lfloor \frac{a}{c} \rfloor]$ 这个区间进行查找即可。

单次询问时间复杂度 $O(\log n)$。

参考代码如下：

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define ll long long
#define writes(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n');
static char buf[100000], * pa(buf), * pb(buf);
int st[114], top;
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void debug(auto st, auto ed, bool endline) {
	for (auto it = st; it != ed; ++it) {
		cout << *it << " ";
	}
	if (endline) cout << '\n';
}
template <typename T> void read(T& x) {
	T t = 0, sgn = 1;
	char ch = gc;
	while (!isdigit(ch)) {
		if (ch == '-') sgn = -sgn;
		ch = gc;
	}
	while (isdigit(ch)) {
		t = (t << 3) + (t << 1) + (ch ^ 48);
		ch = gc;
	}
	x = sgn * t;
}
template <typename T, typename ...Args> void read(T& tmp, Args &...tmps) {
	read(tmp); read(tmps...);
}
template <typename T> void write(T x) {
	if (x < 0) putchar('-'), x = -x;
	top = 0;
	while (x) {
		st[++top] = x % 10;
		x /= 10;
	}
	do {
		putchar(st[top--] + '0');
	} while (top > 0);
}
template <typename T, typename ...Args> void write(T& tmp, Args &...tmps) {
	writes(tmp);
	writes(tmps...);
}
template <typename T> T rand(T l, T r) {
	return rnd() % (r - l + 1) + l;
}
int main() {
	// cin.tie(0)->sync_with_stdio(0);
	// cout.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		ll a, c;
		read(a, c);
		ll l = a / (c + 1) + 1, r = a / c;
		bool ok = 0;
		while (l <= r) {
			ll mid = l + r >> 1;
			if (a / mid == c) {
				ok = 1;
				writeln(a);
				break;
			}
			if (a / mid > c) {
				l = mid + 1;
			}
			else r = mid - 1;
		}
		if (!ok) puts("-1");
	}
}