#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long

int f(int b, int n){
    if(n < b) return n;
    return f(b, n / b) + n % b; 
}

void solve(){
    int x, n;
    cin >> x >> n;
    if(x < n){
        cout << -1 << '\n';
        return;
    }
    if(x == n){
        cout << x + 1 << '\n';
        return;
    }else{
        int sqr = ceil(sqrt(x));
        for(int i = 2; i <= sqr; i++){
            if(f(i, x) == n){
                cout << i << '\n';
                return;
            }
        }
        int ans = -1;
        for(int i = 1; i <= sqr; i++){
            if((x - n) % i == 0 && f((x - n) / i + 1, x) == n){
                ans = (x - n) / i + 1;
            }
        }
        cout << ans << '\n';
    }
}

signed main(){
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}