310305: CF1812D. Trivial Conjecture

D. Trivial Conjecturetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

$$f(n) = \left\{ \begin{array}{ll} \frac{n}{2} & n \equiv 0 \pmod{2}\\ 3n+1 & n \equiv 1 \pmod{2}\\ \end{array} \right.$$

Find an integer $n$ so that none of the first $k$ terms of the sequence $n, f(n), f(f(n)), f(f(f(n))), \dots$ are equal to $1$.

Input

The only line contains an integer $k$ ($1 \leq k \leq \min(\textbf{[REDACTED]}, 10^{18})$).

Output

Output a single integer $n$ such that none of the first $k$ terms of the sequence $n, f(n), f(f(n)), f(f(f(n))), \dots$ are equal to $1$.

Integer $n$ should have at most $10^3$ digits.

ExamplesInput

1

Output

5

Input

5

Output

6

Note

In the first test, the sequence created with $n = 5$ looks like $5, 16, 8, 4, 2, 1, 4, \dots$, and none of the first $k=1$ terms are equal to $1$.

In the second test, the sequence created with $n = 6$ looks like $6, 3, 10, 5, 16, 8, 4, \dots$, and none of the first $k=5$ terms are equal to $1$.

题目大意：给定一个函数 \( f(n) \) 定义如下：

\[ f(n) = \left\{ \begin{array}{ll} \frac{n}{2} & \text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n \equiv 1 \pmod{2} \end{array} \right. \]

需要找到一个整数 \( n \)，使得序列 \( n, f(n), f(f(n)), f(f(f(n))), \dots \) 的前 \( k \) 项都不等于 1。

输入数据格式：输入一个整数 \( k \)（\( 1 \leq k \leq \min(\textbf{[REDACTED]}, 10^{18}) \)）。

输出数据格式：输出一个整数 \( n \)，使得序列的前 \( k \) 项都不等于 1。整数 \( n \) 最多有 \( 10^3 \) 位数字。题目大意：给定一个函数 \( f(n) \) 定义如下： \[ f(n) = \left\{ \begin{array}{ll} \frac{n}{2} & \text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n \equiv 1 \pmod{2} \end{array} \right. \] 需要找到一个整数 \( n \)，使得序列 \( n, f(n), f(f(n)), f(f(f(n))), \dots \) 的前 \( k \) 项都不等于 1。 输入数据格式：输入一个整数 \( k \)（\( 1 \leq k \leq \min(\textbf{[REDACTED]}, 10^{18}) \)）。 输出数据格式：输出一个整数 \( n \)，使得序列的前 \( k \) 项都不等于 1。整数 \( n \) 最多有 \( 10^3 \) 位数字。