


"""simple docstring"""






class     __lowerCamelCase  :

     '''simple docstring'''


     def __init__(      self    ,				__UpperCAmelCase = ""    ,				__UpperCAmelCase = False							)       ->							None:
          # Mapping from the first character of the prefix of the node
          _a    	=				{}

          # A node will be a leaf if the tree contains its word
          _a    	=				is_leaf

          _a    	=				prefix


     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							tuple[str, str, str]:
          _a    	=				0
          for q, w in zip(self.prefix    ,				__UpperCAmelCase							):
               if q != w:
                    break

               x += 1

          return self.prefix[:x], self.prefix[x:], word[x:]


     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							None:
          for word in words:
               self.insert(__UpperCAmelCase							)


     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							None:
          # Case 1: If the word is the prefix of the node
          # Solution: We set the current node as leaf
          if self.prefix == word:
               _a    	=				True

          # Case 2: The node has no edges that have a prefix to the word
          # Solution: We create an edge from the current node to a new one
          # containing the word
          elif word[0] not in self.nodes:
               _a    	=				RadixNode(prefix=__UpperCAmelCase    ,				is_leaf=__UpperCAmelCase							)

          else:
               _a    	=				self.nodes[word[0]]
               _a	,      _a	,      _a    	=				incoming_node.match(
                   __UpperCAmelCase							)

               # Case 3: The node prefix is equal to the matching
               # Solution: We insert remaining word on the next node
               if remaining_prefix == "":
                    self.nodes[matching_string[0]].insert(__UpperCAmelCase							)

               # Case 4: The word is greater equal to the matching
               # Solution: Create a node in between both nodes, change
               # prefixes and add the new node for the remaining word
               else:
                    _a    	=				remaining_prefix

                    _a    	=				self.nodes[matching_string[0]]
                    _a    	=				RadixNode(__UpperCAmelCase    ,				__UpperCAmelCase							)
                    _a    	=				aux_node

                    if remaining_word == "":
                         _a    	=				True
                    else:
                         self.nodes[matching_string[0]].insert(__UpperCAmelCase							)


     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							bool:
          _a    	=				self.nodes.get(word[0]    ,				__UpperCAmelCase							)
          if not incoming_node:
               return False
          else:
               _a	,      _a	,      _a    	=				incoming_node.match(
                   __UpperCAmelCase							)
               # If there is remaining prefix, the word can't be on the tree
               if remaining_prefix != "":
                    return False
               # This applies when the word and the prefix are equal
               elif remaining_word == "":
                    return incoming_node.is_leaf
               # We have word remaining so we check the next node
               else:
                    return incoming_node.find(__UpperCAmelCase							)


     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							bool:
          _a    	=				self.nodes.get(word[0]    ,				__UpperCAmelCase							)
          if not incoming_node:
               return False
          else:
               _a	,      _a	,      _a    	=				incoming_node.match(
                   __UpperCAmelCase							)
               # If there is remaining prefix, the word can't be on the tree
               if remaining_prefix != "":
                    return False
               # We have word remaining so we check the next node
               elif remaining_word != "":
                    return incoming_node.delete(__UpperCAmelCase							)
               else:
                    # If it is not a leaf, we don't have to delete
                    if not incoming_node.is_leaf:
                         return False
                    else:
                         # We delete the nodes if no edges go from it
                         if len(incoming_node.nodes							) == 0:
                              del self.nodes[word[0]]
                              # We merge the current node with its only child
                              if len(self.nodes							) == 1 and not self.is_leaf:
                                   _a    	=				list(self.nodes.values()							)[0]
                                   _a    	=				merging_node.is_leaf
                                   self.prefix += merging_node.prefix
                                   _a    	=				merging_node.nodes
                    # If there is more than 1 edge, we just mark it as non-leaf
                         elif len(incoming_node.nodes							) > 1:
                              _a    	=				False
                         # If there is 1 edge, we merge it with its child
                         else:
                              _a    	=				list(incoming_node.nodes.values()							)[0]
                              _a    	=				merging_node.is_leaf
                              incoming_node.prefix += merging_node.prefix
                              _a    	=				merging_node.nodes

                         return True





     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase = 0							)       ->							None:
          if self.prefix != "":
               print('''-''' * height    ,				self.prefix    ,				'''  (leaf)''' if self.is_leaf else ''''''							)

          for value in self.nodes.values():
               value.print_tree(height + 1							)







def       A_   (   ):






     """simple docstring"""

     _a    	=				'''banana bananas bandana band apple all beast'''.split()
     _a    	=				RadixNode()
     root.insert_many(_lowerCAmelCase       )

     assert all(root.find(_lowerCAmelCase       ) for word in words       )
     assert not root.find('''bandanas'''       )
     assert not root.find('''apps'''       )
     root.delete('''all'''       )
     assert not root.find('''all'''       )
     root.delete('''banana'''       )
     assert not root.find('''banana'''       )
     assert root.find('''bananas'''       )

     return True
def       A_   (   ):






     """simple docstring"""

     assert test_trie()
def       A_   (   ):






     """simple docstring"""

     _a    	=				RadixNode()
     _a    	=				'''banana bananas bandanas bandana band apple all beast'''.split()
     root.insert_many(_lowerCAmelCase       )

     print('''Words:''',     _lowerCAmelCase       )
     print('''Tree:'''       )
     root.print_tree()


if __name__ == "__main__":
   main()



"""simple docstring"""






def       A_   (   _lowerCAmelCase     :					int = 10_00       ):






     """simple docstring"""

     _a	,      _a    	=				1, 1
     _a    	=				2
     while True:
          _a    	=				0
          _a    	=				fa + fa
          _a	,      _a    	=				fa, f
          index += 1
          for _ in str(_lowerCAmelCase       ):
               i += 1
          if i == n:
               break
     return index


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