AT_past202107_e 青木君のいたずら

[problemUrl]: https://atcoder.jp/contests/past202107-open/tasks/past202107_e 初期値が $ 1 $ の変数 $ X $ があります。 高橋君は、変数 $ X $ に対して、「 $ X $ を $ 3 $ 倍する」という操作を $ 30 $ 回行いました。 しかし、操作の結果 $ X $ は $ 3^{30} $ とはならず、$ N $ という値になってしまいました。 いたずら好きな青木君が、以下の操作をしたことを白状しました。 - $ 1\ \leq\ k\ \leq\ 30 $ であるような整数 $ k $ を $ 1 $ つだけ選び、高橋君の $ k $ 回目の操作の直後に変数 $ X $ に $ 1 $ を加算した。 $ N $ が与えられるので、$ k $ を求めてください。 ただし、どのような $ k $ に対しても操作の結果として $ X $ が $ N $ とはならない場合、$ -1 $ と出力してください。

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

答えを出力せよ。 ただし、どのような $ k $ に対しても操作の結果 $ X $ が $ N $ とはならない場合、$ -1 $ と出力せよ。

### 注意 この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leq\ N\ \leq\ 10^{15} $ - $ N\ \neq\ 3^{30} $ - 入力は全て整数である。 ### Sample Explanation 1 $ k=10 $ の場合の挙動を示します。 $ 1 $ を $ 10 $ 回 $ 3 $ 倍すると $ 59049 $ になります。 青木君のいたずらにより $ 1 $ を加算して $ 59050 $ になります。 さらに、$ 20 $ 回 $ 3 $ 倍すると $ 205894618879050 $ になります。