rt

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long

int a, k;
int sum;

signed main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        cin >> a >> k;
        if (a < k) cout << -1 << "\n";
        else {
            int l = 1, r = a, mid;
            while (l < r) {
                mid = (l + r + 1) / 2;
                if (k * mid > a) r = mid - 1;
                else l = mid;
            }
            if (a / l == k) cout << a << "\n";
            else cout << -1 << "\n";
        }

    }
    return 0;
}