




from __future__ import annotations

import math
import random
from typing import Any




class 		UpperCamelCase__	:

    '''simple docstring'''



    def __init__(    self     )     ->      None:
           lowerCamelCase   :      list[Any]			 =					[]
           lowerCamelCase   :      int			 =					0
           lowerCamelCase   :      int			 =					0







    def     _lowercase     (    self     )     ->      bool:
           return self.head == self.tail







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           self.data.append(UpperCamelCase__     )
           lowerCamelCase   :      Union[str, Any]			 =					self.tail + 1







    def     _lowercase     (    self     )     ->      Any:
           lowerCamelCase   :      Optional[int]			 =					self.data[self.head]
           lowerCamelCase   :      List[Any]			 =					self.head + 1
           return ret







    def     _lowercase     (    self     )     ->      int:
           return self.tail - self.head







    def     _lowercase     (    self     )     ->      None:
           print(self.data     )
           print("**************"     )
           print(self.data[self.head : self.tail]     )




class 		UpperCamelCase__	:

    '''simple docstring'''



    def __init__(    self     ,  UpperCamelCase__     )     ->      None:
           lowerCamelCase   :      str			 =					data
           lowerCamelCase   :      MyNode | None			 =					None
           lowerCamelCase   :      MyNode | None			 =					None
           lowerCamelCase   :      int			 =					1







    def     _lowercase     (    self     )     ->      Any:
           return self.data







    def     _lowercase     (    self     )     ->      MyNode | None:
           return self.left







    def     _lowercase     (    self     )     ->      MyNode | None:
           return self.right







    def     _lowercase     (    self     )     ->      int:
           return self.height







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           lowerCamelCase   :      int			 =					data







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           lowerCamelCase   :      Dict			 =					node







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           lowerCamelCase   :      Optional[int]			 =					node







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           lowerCamelCase   :      str			 =					height




def      A      (      _SCREAMING_SNAKE_CASE    )	-> int:
       if node is None:
              return 0
       return node.get_height()

def      A      (      _SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )	-> int:
       if a > b:
              return a
       return b

def      A      (      _SCREAMING_SNAKE_CASE    )	-> MyNode:
       print("left rotation node:" ,node.get_data()    )
       lowerCamelCase   :      Optional[Any]			 =					node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()    )
       ret.set_right(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      Dict			 =					my_max(get_height(node.get_right()    ) ,get_height(node.get_left()    )    ) + 1
       node.set_height(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      Optional[int]			 =					my_max(get_height(ret.get_right()    ) ,get_height(ret.get_left()    )    ) + 1
       ret.set_height(_SCREAMING_SNAKE_CASE    )
       return ret

def      A      (      _SCREAMING_SNAKE_CASE    )	-> MyNode:
       print("right rotation node:" ,node.get_data()    )
       lowerCamelCase   :      str			 =					node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()    )
       ret.set_left(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      Tuple			 =					my_max(get_height(node.get_right()    ) ,get_height(node.get_left()    )    ) + 1
       node.set_height(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      Optional[Any]			 =					my_max(get_height(ret.get_right()    ) ,get_height(ret.get_left()    )    ) + 1
       ret.set_height(_SCREAMING_SNAKE_CASE    )
       return ret

def      A      (      _SCREAMING_SNAKE_CASE    )	-> MyNode:
       lowerCamelCase   :      str			 =					node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(_SCREAMING_SNAKE_CASE    )    )
       return right_rotation(_SCREAMING_SNAKE_CASE    )

def      A      (      _SCREAMING_SNAKE_CASE    )	-> MyNode:
       lowerCamelCase   :      Any			 =					node.get_right()
       assert right_child is not None
       node.set_right(right_rotation(_SCREAMING_SNAKE_CASE    )    )
       return left_rotation(_SCREAMING_SNAKE_CASE    )

def      A      (      _SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )	-> MyNode | None:
       if node is None:
              return MyNode(_SCREAMING_SNAKE_CASE    )
       if data < node.get_data():
              node.set_left(insert_node(node.get_left() ,_SCREAMING_SNAKE_CASE    )    )
              if (
                  get_height(node.get_left()    ) - get_height(node.get_right()    ) == 2
              ):  # an unbalance detected
                     lowerCamelCase   :      Optional[Any]			 =					node.get_left()
                     assert left_child is not None
                     if (
                         data < left_child.get_data()
                     ):  # new node is the left child of the left child
                            lowerCamelCase   :      List[Any]			 =					right_rotation(_SCREAMING_SNAKE_CASE    )
                     else:
                            lowerCamelCase   :      List[str]			 =					lr_rotation(_SCREAMING_SNAKE_CASE    )
       else:
              node.set_right(insert_node(node.get_right() ,_SCREAMING_SNAKE_CASE    )    )
              if get_height(node.get_right()    ) - get_height(node.get_left()    ) == 2:
                     lowerCamelCase   :      List[Any]			 =					node.get_right()
                     assert right_child is not None
                     if data < right_child.get_data():
                            lowerCamelCase   :      Optional[Any]			 =					rl_rotation(_SCREAMING_SNAKE_CASE    )
                     else:
                            lowerCamelCase   :      Optional[Any]			 =					left_rotation(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      Any			 =					my_max(get_height(node.get_right()    ) ,get_height(node.get_left()    )    ) + 1
       node.set_height(_SCREAMING_SNAKE_CASE    )
       return node

def      A      (      _SCREAMING_SNAKE_CASE    )	-> Any:
       while True:
              lowerCamelCase   :      List[str]			 =					root.get_right()
              if right_child is None:
                     break
              lowerCamelCase   :      List[str]			 =					right_child
       return root.get_data()

def      A      (      _SCREAMING_SNAKE_CASE    )	-> Any:
       while True:
              lowerCamelCase   :      str			 =					root.get_left()
              if left_child is None:
                     break
              lowerCamelCase   :      List[str]			 =					left_child
       return root.get_data()

def      A      (      _SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )	-> MyNode | None:
       lowerCamelCase   :      int			 =					root.get_left()
       lowerCamelCase   :      int			 =					root.get_right()
       if root.get_data() == data:
              if left_child is not None and right_child is not None:
                     lowerCamelCase   :      Dict			 =					get_left_most(_SCREAMING_SNAKE_CASE    )
                     root.set_data(_SCREAMING_SNAKE_CASE    )
                     root.set_right(del_node(_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )    )
              elif left_child is not None:
                     lowerCamelCase   :      Union[str, Any]			 =					left_child
              elif right_child is not None:
                     lowerCamelCase   :      Dict			 =					right_child
              else:
                     return None
       elif root.get_data() > data:
              if left_child is None:
                     print("No such data"    )
                     return root
              else:
                     root.set_left(del_node(_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )    )
       else:  # root.get_data() < data
              if right_child is None:
                     return root
              else:
                     root.set_right(del_node(_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )    )

       if get_height(_SCREAMING_SNAKE_CASE    ) - get_height(_SCREAMING_SNAKE_CASE    ) == 2:
              assert right_child is not None
              if get_height(right_child.get_right()    ) > get_height(right_child.get_left()    ):
                     lowerCamelCase   :      Union[str, Any]			 =					left_rotation(_SCREAMING_SNAKE_CASE    )
              else:
                     lowerCamelCase   :      int			 =					rl_rotation(_SCREAMING_SNAKE_CASE    )
       elif get_height(_SCREAMING_SNAKE_CASE    ) - get_height(_SCREAMING_SNAKE_CASE    ) == -2:
              assert left_child is not None
              if get_height(left_child.get_left()    ) > get_height(left_child.get_right()    ):
                     lowerCamelCase   :      Tuple			 =					right_rotation(_SCREAMING_SNAKE_CASE    )
              else:
                     lowerCamelCase   :      Any			 =					lr_rotation(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      str			 =					my_max(get_height(root.get_right()    ) ,get_height(root.get_left()    )    ) + 1
       root.set_height(_SCREAMING_SNAKE_CASE    )
       return root




class 		UpperCamelCase__	:

    '''simple docstring'''



    def __init__(    self     )     ->      None:
           lowerCamelCase   :      MyNode | None			 =					None







    def     _lowercase     (    self     )     ->      int:
           return get_height(self.root     )







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           print("insert:" + str(UpperCamelCase__     )     )
           lowerCamelCase   :      Dict			 =					insert_node(self.root     ,  UpperCamelCase__     )







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      None:
           print("delete:" + str(UpperCamelCase__     )     )
           if self.root is None:
                  print("Tree is empty!"     )
                  return
           lowerCamelCase   :      Tuple			 =					del_node(self.root     ,  UpperCamelCase__     )







    def __str__(    self     ,  )     ->      str:  # a level traversale, gives a more intuitive look on the tree
           lowerCamelCase   :      Tuple			 =					""
           lowerCamelCase   :      Optional[int]			 =					MyQueue()
           q.push(self.root     )
           lowerCamelCase   :      str			 =					self.get_height()
           if layer == 0:
                  return output
           lowerCamelCase   :      Any			 =					0
           while not q.is_empty():
                  lowerCamelCase   :      List[Any]			 =					q.pop()
                  lowerCamelCase   :      Optional[Any]			 =					" " * int(math.pow(2     ,  layer - 1     )     )
                  output += space
                  if node is None:
                         output += "*"
                         q.push(UpperCamelCase__     )
                         q.push(UpperCamelCase__     )
                  else:
                         output += str(node.get_data()     )
                         q.push(node.get_left()     )
                         q.push(node.get_right()     )
                  output += space
                  lowerCamelCase   :      Dict			 =					cnt + 1
                  for i in range(100     ):
                         if cnt == math.pow(2     ,  UpperCamelCase__     ) - 1:
                                lowerCamelCase   :      Optional[int]			 =					layer - 1
                                if layer == 0:
                                       output += "\n*************************************"
                                       return output
                                output += "\n"
                                break
           output += "\n*************************************"
           return output




def      A      (      )	-> None:
       import doctest

       doctest.testmod()


if __name__ == "__main__":
       _test()
       SCREAMING_SNAKE_CASE__       :      Any  =   AVLtree()
       SCREAMING_SNAKE_CASE__       :      Union[str, Any]  =   list(range(10))
       random.shuffle(lst)
       for i in lst:
              t.insert(i)
              print(str(t))
       random.shuffle(lst)
       for i in lst:
              t.del_node(i)
              print(str(t))












def      A      (      _SCREAMING_SNAKE_CASE = 100_0000    )	-> int:
       lowerCamelCase   :      Tuple			 =					1
       lowerCamelCase   :      int			 =					1
       lowerCamelCase   :      Optional[Any]			 =					{1: 1}

       for inputa in range(2 ,_SCREAMING_SNAKE_CASE    ):
              lowerCamelCase   :      Union[str, Any]			 =					0
              lowerCamelCase   :      List[str]			 =					inputa

              while True:
                     if number in counters:
                            counter += counters[number]
                            break
                     if number % 2 == 0:
                            number //= 2
                            counter += 1
                     else:
                            lowerCamelCase   :      str			 =					(3 * number) + 1
                            counter += 1

              if inputa not in counters:
                     lowerCamelCase   :      str			 =					counter

              if counter > pre_counter:
                     lowerCamelCase   :      str			 =					inputa
                     lowerCamelCase   :      Any			 =					counter
       return largest_number


if __name__ == "__main__":
       print(solution(int(input().strip())))






