//
//  na 2684-re.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/21.
//

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long int ll;
ll x, n;
inline ll ds(ll base){
    ll res = 0, reg = x;
    while(reg){
        res += reg % base;
        reg /= base;
    }
//    cerr << "ds-" << base << " -> " << res << endl;
    return res;
}
inline ll solve(){
    cin >> x >> n;
    {
        ll s = 0;
        for(ll i = 0; i < 61; ++i)
            s += (x >> i) & 1;
        if(s == n)
            return 2;
//        cerr << "NOT BINARY" << endl;
    }
    if(n == x)
        return x + 1;
    ll lim = x, lt, rt, mid, res = -1, base, slope, dst;
    while(lim > 2){
//        cerr << "test" << lim << endl;
        base = ds(lim);
        if(base == n)
            res = lim;
        slope = ds(lim - 1) - ds(lim);
        if(slope <= 0){
            --lim;
            continue;
        }
        lt = 1; rt = lim - 1;
        while(lt < rt - 1){
            mid = (lt + rt) >> 1;
            if(ds(mid) == base + slope * (lim - mid))
                rt = mid;
            else
                lt = mid;
        }
//        cerr << "found interval: " << lt << " -> " << lim << endl;
        if(base <= n && (n - base) % slope == 0){
            dst = lim - (n - base) / slope;
            if(dst >= rt)
                res = min(res, dst);
        }
        lim = rt - 1;
    }
    return res;
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)
        cout << solve() << endl;
    return 0;
}