#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll calc(ll x,ll k){
    ll re=0;
    while(x){
        re+=x%k;x/=k;
    }
    return re;
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        ll x,n;cin>>x>>n;//swap(n,s);
        ll ans=0;
        if(x==n){
            cout<<(x+1)<<endl;
            continue;
        }
        if(n>x){
            puts("-1");
            continue;
        }
        for(ll i=2;i*i<=x;++i)if(calc(x,i)==n){ans=i;break;}
        if(ans){
            cout<<ans<<endl;
            continue;
        }
        ans=1e18;
        for(ll i=1;i*i<=x-n;++i){
            if((x-n)%i)continue;
            ll an=(x-n)/i;
            if(calc(x,an+1)==n)ans=min(ans,an+1);
            if(calc(x,i+1)==n)ans=min(ans,i+1);
        }
        if(ans==1e18){puts("-1");continue;}
        printf("%lld\n",ans);
    }
    return 0;
}