#include <bits/stdc++.h>
#define int long long 
using namespace std;
int calc(int val, int b){
    int res = 0;
    while(val){
        res += val % b;
        val /= b;
    }
    return res;
}
void sol(){
    int x, n;cin >> x >> n;
    if(x < n){
        cout << -1 << endl;
        return ;
    }
    if(x == n){
        cout << x + 1 << endl;
        return ;
    }
    int sq = sqrt(x) + 10;
    for(int i = 2;i <= sq;i++){
        if(calc(x, i) == n){
            cout << i << endl;
            return ;
        }
    }
    for(int i = sq;i;i--){
        if((x - n) % i) continue;
        int b = (x - n) / i + 1;
        if(calc(x, b) == n){
            cout << b << endl;
            return ;
        }
    }
    cout << -1 << endl;
}
int32_t main(){
    int cas;cin >> cas;while(cas--) sol();
    return 0;
}