#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
ll n,s;
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
ll f(ll a, ll b){ll res=0;while(a){res+=a%b;a/=b;}return res;}
void solve(){
    n=read();s=read();
    if(n<s){write(-1);putchar('\n');return;}
    if(n==s){write(n+1);putchar('\n');return;}
    for(int i=2; i<=sqrt(n); i++) if(f(n,i)==s){write(i);putchar('\n');return;}
    for(int i=sqrt(n); i>=1; i--) if((n-s)%i==0&&f(n,(n-s)/i+1)==s){write((n-s)/i+1);putchar('\n');return;}
}
int main(){
    ll T=read();while(T--)solve();
    return 0;
}
//n=bx+y
//s=x+y
//n-s=(b-1)x