You cannot submit for this problem because the homework's deadline is due.

Description

Let the sequence \((u_n)_{n\geqslant 0}\) of integers be defined by

\[\left\{ \begin{aligned} u_0 &= a \\ u_{i+1} &= \left\{ \begin{aligned} \frac12u_i, &\qquad {\rm if}\ u_i\ {\rm is\ even} \\ 3u_i+1, &\qquad {\rm if}\ u_i\ {\rm is\ odd} \end{aligned} \right. \end{aligned} \right.\]

1. Write a function which prompts the user for \(a\) and determines \(N\) such that \(u_N = 1\).

2. Write a function which prompts the user for a value \(M\), and returns \(A\), the value of \(2 \leqslant a \leqslant M\), such that \(N\) is maximized.

Format

Files

You should submit a tar file containing a c++ source file ex4.cpp

Input

two lines, the first one being 1 or 2 for the function from question 1 or 2, respectively, and
an integer corresponding to \(a\) or \(M\) on the second one
We garantee that M <= 10000000 and calculations will not exceed 2^64 - 1.

Output

one line showing the result

Sample 1

Input

1
1

Output

0

Limitation

2s, 256MiB for each test case.

Hint

256MiB is very large and you may use recursion and record Ns for intermediate results.