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

File

Sample Makefile and CMakelists for cpp has been uploaded to canvas (under extra folder). Also, you need to use cpp template for hw7 (under extra folder)

GNUMake

If you choose GNUMake, then you should compress assignment.h, ex1.cpp, ex2.cpp, ex4.cpp, main.cpp, Makefile directly into a zip and submit this zip. (A sample Makefile for hw7 is uploaded on Canvas).

If you just finished ex4 and you immediately want to test whether your ex4 is working correctly. You need to modify your main.cpp, assignment.h, Makefile and then compress main.cpp,assignment.h,Makefile,ex4.cpp into a zip and submit this zip.

The sample Makefile on Canvas has -o main, do not change this main!

CMake

If you choose CMake, then you should compress assignment.h, ex1.cpp, ex2.cpp, ex4.cpp, main.cpp, CMakeLists.txt directly into a zip and submit this zip. (A sample CMakeLists.txt for hw7 is uploaded on Canvas).

If you just finished ex4 and you immediately want to test whether your ex4 is working correctly. You need to modify your main.cpp, assignment.h, CMakeLists.txt and then compress main.cpp,assignment.h,CMakeLists.txt,ex4.cpp into a zip and submit this zip.

The sample CMakeLists.txt on Canvas has add_executable(main ..., do not change this main! Also, do not change cmake_minimum_required(VERSION 2.7)

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

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.