001 - コラッツ予想

時間制限 1 秒 / メモリ制限 32 MB / 得点 5 / x 23 /


TLE
1sec
MLE
32MB
得点
5

問題

自然数から新たな自然数を作る次のような関数 f を考える。

  • n が奇数のとき、f(n) = 3n + 1
  • n が偶数のとき、f(n) = n / 2

1 以上の自然数 m に対して、ft(m) = 1 となるような最小の非負整数 tt(m) と書くことにする。m が与えられるので、t(m) を求めよ。

ただし、ft(m) とは mft 回適用したものを表す。

入力

入力は 1 行のみからなり、その行には 1 つの自然数 m が含まれる。

1 ≤ m ≤ 109 であり、任意の非負整数 k に対して fk(m) ≤ 1018 であることが保証されている。

出力

t(m) を 1 行に出力せよ。もし ft(m) = 1 となるような t が存在しない場合、"Counterexample for Collatz conjecture!" と 1 行に出力せよ。

入力例

42
7
1
525858345
670617279

出力例

8
16
0
585
986