/** * author: mackerel38 * created: 05.09.2025 22:00:11 **/ #line 2 "library/util/template.hpp" #ifdef poe #define debug(x) cerr<<#x<<": "< using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; using pi=pair; using pll=pair; using str=string; templateusing vec=vector; using vi=vec;using vvi=vec;using vvvi=vec;using vvvvi=vec;using vvvvvi=vec; using vll=vec;using vvll=vec;using vvvll=vec;using vvvvll=vec;using vvvvvll=vec; using vpi=vec;using vvpi=vec;using vvvpi=vec;using vvvvpi=vec;using vvvvvpi=vec; using vpll=vec;using vvpll=vec;using vvvpll=vec;using vvvvpll=vec;using vvvvvpll=vec; templateusing pq=priority_queue>; templateusing pqg=priority_queue,greater>; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define per(i,n) for(int i=(int)(n)-1;0<=i;i--) #define per1(i,n) for(int i=(int)(n);0>(i))&1) #define pf push_front #define pb push_back #define df pop_front #define db pop_back #define fi first #define se second #define elif else if #define Yes cout<<"Yes"<<'\n' #define No cout<<"No"<<'\n' #define YN(x) cout<<((x)?"Yes":"No")<<'\n' #define O(x) cout<<(x)<<'\n' #define ismid(a,b,c) ((a)<=(b)&&(b)<(c)) templatebool chmin(S&a,T b){if(a>b){a=b;return true;}return false;} templatebool chmax(S&a,T b){if(abool next_combination(T l,T r,int k){T m=l+k;if(l==r||l==m||r==m)return false;T t=m;while(l!=t){t--;if(*t<*(r-1)){T d=m;while(*t>=*d)d++;iter_swap(t,d);rotate(t+1,d+1,r);rotate(m,m+(r-d)-1,r);return true;}}rotate(l,m,r);return false;} templateT Min(T a,T b){return aT Min(T a,T b,Args...args){return Min(Min(a,b),args...);} templateT Max(T a,T b){return a>b?a:b;} templateT Max(T a,T b,Args...args){return Max(Max(a,b),args...);} templateT Sum(T a){return a;} templateT Sum(T a,Args... args){return a+Sum(args...);} templateT Max(const vector&v){return *max_element(all(v));} templateT Min(const vector&v){return *min_element(all(v));} templateT Sum(const vector&v){return accumulate(all(v),T(0));} templateT Max(const pair&p){return max(p.first,p.second);} templateT Min(const pair&p){return min(p.first,p.second);} templateT Sum(const pair&p){return p.first+p.second;} templateistream&operator>>(istream&s,pair&p){s>>p.first>>p.second;return s;} templateostream&operator<<(ostream&s,pair&p){s<istream&operator>>(istream&s,vector&v){for(auto&i:v)s>>i;return s;} templateostream&operator<<(ostream&s,vector&v){for(auto&i:v)s<long long bsearch(long long ok,long long ng,F&f){while(abs(ok-ng)>1){long long mid=(ok+ng)/2;if(f(mid))ok=mid;else ng=mid;}return ok;} const int dxy[5]={0,1,0,-1,0}; const int dx[8]={0,1,0,-1,1,1,-1,-1}; const int dy[8]={1,0,-1,0,1,-1,1,-1}; #define nl '\n' #define sp ' ' #define inf ((1<<30)-(1<<15)) #define INF (1LL<<61) #define mod 998244353 void IO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout<> tests = {{2, 7, 61}, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}}; long long s = 0, d = n - 1; while (d % 2 == 0) { ++s; d >>= 1; } for (auto a : tests[flag]) { if (n <= a) return true; __int128_t x = 1, a2=a%n, d2 = d; while (d2) { if (d2 & 1) x = x * a2 % n; a2 = a2 * a2 % n; d2 >>= 1; } if (x != 1) { long long t; for (t = 0; t < s; ++t) { if (x == n - 1) break; x = x * x % n; } if (t == s) return false; } } return true; } // n 以下の素数を列挙する O(n log log n) vector enumprimes(int n) { vector primeflag(n+1); vector re; for (long long i=2; i<=n; i++) { if (primeflag[i]) continue; re.push_back(i); for (long long j=i*i; j<=n; j+=i) { primeflag[j] = true; } } return re; } // 素因数分解をする O(n^0.25) void factorize(long long n, vector& factors) { if (n <= 1) return; if (isprime(n)) { factors.push_back(n); return; } if (n % 2 == 0) { while (n % 2 == 0) { factors.push_back(2); n /= 2; } factorize(n, factors); return; } while (true) { __int128_t x = rand() % (n - 2) + 2; __int128_t y = x; __int128_t c = rand() % (n - 1) + 1; __int128_t m = 1; while (m == 1) { x = (x * x + c) % n; y = (y * y + c) % n; y = (y * y + c) % n; m = gcd((long long)(x - y + n), n); if (m == n) break; } if (m != n) { factorize(m, factors); factorize(n / m, factors); return; } } } #line 3 "library/math/isqrt.hpp" using namespace std; // floor(sqrt(n)) を返す long long isqrt(long long n) { assert(0 <= n); long long re = sqrt(n); while ((re + 1) * (re + 1) <= n) re++; while (n < re * re) re--; return re; } #line 4 "contests/abc059/a/main.cpp" int main() { IO(); int T=1; cin >> T; while (T--) solve(); } void solve() { ll n, k; cin >> n >> k; if (n == k) { cout << -1 << nl; return; } n++; while (n--) { bool flag = false; for (ll i=1; i*i<=n&&i<=k; i++) { if (n%i == 0 && n/i<=k) flag = true; if (flag) break; } if (!flag) { cout << n << nl; return; } } }