Problem F. 考拉兹猜想——怎么又是你

时间限制：1s

空间限制：256MB

题目背景

考拉兹猜想 是 1937 年 Lothar Collatz 提出的，也叫 3$n$+1 猜想。数学家 Paul Erdos 曾这样评价这个猜想：「Mathematics may not be ready for such problems」.

命题陈述为：对任意正整数 $n$ （ $n$∈$Z^+$ ），若 $n$ 为偶数则除以 2 ，若 $n$ 为奇数则乘 3 再加 1 ，如此反复，其结果最终必会达到 1 .

稍正式的表述：$f(n) = \left\{ \begin{array}{ccl} \frac{n}{2} & & {n \equiv 0 (mod \ 2)}\\ 3n+1 & & {n \equiv 1 (mod \ 2)}\\ \end{array} \right. $，必有 $k$∈$N$ 使得 $f^k(n)=1$ .

题目描述

纳西妲试了在 int 范围内的所有正整数，发现考拉兹猜想都成立，于是她便放弃了寻找反例的想法。不过纳西妲又想到一个新问题：是否存在一个正整数 $n$ ，在经过 $k$ 次调用后，恰好可以得到 $f^k(n) = 1$ 呢？

输入描述

输入一个整数 $k$。

$1 \le k \le 10^9$

输出描述

输出一个满足条件的正整数 $n$ ，使得 $f^k(n) = 1$。

输出的正整数 $n$ 需要满足 $1 \le n \le 10^6$。

如果有多个满足条件的整数，输出其中任意一个即可。

样例1

输入

9

输出

12

解释

$n = 12$ 的 Collatz 序列为：12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

样例2

输入

111

输出

27