配点 : $500$ 点

問題文

$2$ 以上の整数 $b$ および $1$ 以上の整数 $n$ に対し、関数 $f(b,n)$ を次のように定義します。

• $n < b$ のとき $f(b,n) = n$
• $n \geq b$ のとき $f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b)$

ここで、${\rm floor}(n / b)$ は $n / b$ を超えない最大の整数を、 $n \ {\rm mod} \ b$ は $n$ を $b$ で割った余りを表します。

直感的に言えば、$f(b,n)$ は、$n$ を $b$ 進表記したときの各桁の和となります。 例えば、

• $f(10,\,87654)=8+7+6+5+4=30$
• $f(100,\,87654)=8+76+54=138$

などとなります。

整数 $n$ と $s$ が与えられます。 $f(b,n)=s$ を満たすような $2$ 以上の整数 $b$ が存在するか判定してください。 さらに、そのような $b$ が存在するならば、その最小値を求めてください。

制約

• $1 \leq n \leq 10^{11}$
• $1 \leq s \leq 10^{11}$
• $n,\,s$ はいずれも整数である

入力

入力は以下の形式で標準入力から与えられる。

$n$

$s$

出力

$f(b,n)=s$ を満たす $2$ 以上の整数 $b$ が存在するならば、そのような $b$ の最小値を出力せよ。 そのような $b$ が存在しないならば、代わりに -1 を出力せよ。

87654
30

10

87654
138

100

87654
45678

-1

31415926535
1

31415926535

1
31415926535

-1