#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

i64 solve(i64 X, i64 N) {
    i64 m, mr;
    for (m = 2; m * m <= X; m ++) {
        i64 x = X, n = 0;
        for (; x; x /= m) n += x % m;
        if (n == N) return m;
    }
    for (; m <= X; m = mr + 1) {
        i64 a = X / m, b = N - a;
        mr = X / a;
        if (b >= 0 && (X - b) % a == 0) {
            i64 mm = (X - b) / a;
            if (mm <= mr) return mm;
        }
    }
    return X == N ? X + 1 : -1;
}

int main() {
    i64 T, X, N, M;
    for (scanf("%lld", &T); T --; ) {
        scanf("%lld%lld", &X, &N);
        M = solve(X, N);
        printf("%lld\n", M);
    }
    return 0;
}