#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
long long t, x, n;
long long solve(long long x, long long b) {
    long long sum = 0;
    while (x) {
        sum += x % b;
        x /= b;
    }
    return sum;
}
int main() {
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld%lld", &x, &n);
        if (x < n) {
            printf("-1\n");
            continue;
        }
        if (x == n) {
            printf("%lld\n", x + 1);
        }
        bool flag = false;
        for (int i = 2; i * i <= x; i++) {
            if (solve(x, i) == n) {
                printf("%lld\n", i);
                flag = true;
                break;
            }
        }
        if (flag) {
            continue;
        }
        for (int i = min((long long)sqrt(x), n); i >= 1; i--) {
            long long j = n - i;
            if ((x - j) % i == 0) {
                long long y = (x - j) / i;
                if (y > i && y > j) {
                    printf("%lld\n", y);
                    flag = true;
                    break;
                }
            }
        }
        if (!flag) {
            printf("-1\n");
        }
    }
    return 0;
}