C - N進数

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

10 以上の整数 N に対し、 N 進数で N と表現できる数字を f(N) とします。

例えば、 f(23) は、2 × 23 + 3 = 49 のように求めることが出来ます。

整数 A が与えられます。この数字が、f(k) のような形で表すことが可能かどうかを調べたいです。

整数 A が、 10 以上の整数 k を用いて、 f(k) の形で表すことが可能であれば、k を出力し、そうでなければ -1 を出力してください。


入力

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

A
  • 1 行目には、整数 A(1 ≦ A ≦ 10^{16}) が与えられる。

出力

整数 A10 以上の整数 k を用いて、 f(k) の形で表すことが可能であれば、k を出力し、そうでなければ -1 を出力せよ。出力の末尾には改行をいれること。


入力例1

49

出力例1

23

サンプルで与えられた通りです。


入力例2

999999999999999

出力例2

-1

大きな入力が与えられることもあります。


入力例3

10000000000000000

出力例3

10000