F - コラッツ問題

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

整数 X に対し、値 f(X) を以下のように定義します。

  • X ≧ 10^{16} のとき、f(X) = 0
  • 上記以外で X ≦ 1 のとき、f(X) = 0
  • 上記以外で X が偶数のとき、 f(X) = f(X/2) + 1
  • 上記以外のとき、f(X) = f(3X + 1) + 1

整数 P が与えられます。f(N) = P となるような 10^{16} 以下の正整数 N をいずれか 1 つ出力してください。

制約

  • 0 ≦ P ≦ 1,000

入力

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

P

出力

題意を満たす整数 N を出力せよ。そのような整数が複数存在するときは、そのうちのいずれを出力してもよい。なお、この問題の制約下でそのような整数が必ず存在することが示せる。


入力例 1

5

出力例 1

5

入力例 2

1000

出力例 2

1789997546303