题目背景

考拉兹猜想 是 1937 年 Lothar Collatz 提出的，也叫 ~3n+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