






'''simple docstring'''



from __future__ import annotations

import time

__UpperCamelCase   :							List[str]         =   list[tuple[int, int]]

__UpperCamelCase   :							str         =   [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__UpperCamelCase   :							List[Any]         =   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right
class 				__SCREAMING_SNAKE_CASE							:




      def __init__(	self			, lowerCamelCase			, lowerCamelCase			, lowerCamelCase			, lowerCamelCase			, lowerCamelCase   )				->Any:



         '''simple docstring'''
         __a					  =     pos_x
         __a					  =     pos_y
         __a					  =     (pos_y, pos_x)
         __a					  =     goal_x
         __a					  =     goal_y
         __a					  =     parent







class 				__SCREAMING_SNAKE_CASE							:




      def __init__(	self			, lowerCamelCase			, lowerCamelCase   )				->int:



         '''simple docstring'''
         __a					  =     Node(start[1]			, start[0]			, goal[1]			, goal[0]			, SCREAMING_SNAKE_CASE_   )
         __a					  =     Node(goal[1]			, goal[0]			, goal[1]			, goal[0]			, SCREAMING_SNAKE_CASE_   )

         __a					  =     [self.start]
         __a					  =     False




      def 			__UpperCamelCase				(	self   )				->List[str]:



         '''simple docstring'''




         while self.node_queue:
            __a					  =     self.node_queue.pop(0   )

            if current_node.pos == self.target.pos:
               __a					  =     True
               return self.retrace_path(SCREAMING_SNAKE_CASE_   )

            __a					  =     self.get_successors(SCREAMING_SNAKE_CASE_   )

            for node in successors:
               self.node_queue.append(SCREAMING_SNAKE_CASE_   )

         if not self.reached:
            return [self.start.pos]
         return None




      def 			__UpperCamelCase				(	self			, lowerCamelCase   )				->Union[str, Any]:



         '''simple docstring'''
         __a					  =     []
         for action in delta:
            __a					  =     parent.pos_x + action[1]
            __a					  =     parent.pos_y + action[0]
            if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(SCREAMING_SNAKE_CASE_   ) - 1):
               continue

            if grid[pos_y][pos_x] != 0:
               continue

            successors.append(
                Node(SCREAMING_SNAKE_CASE_			, SCREAMING_SNAKE_CASE_			, self.target.pos_y			, self.target.pos_x			, SCREAMING_SNAKE_CASE_   )   )
         return successors






      def 			__UpperCamelCase				(	self			, lowerCamelCase   )				->Any:



         '''simple docstring'''
         __a					  =     node
         __a					  =     []
         while current_node is not None:
            path.append((current_node.pos_y, current_node.pos_x)   )
            __a					  =     current_node.parent
         path.reverse()
         return path







class 				__SCREAMING_SNAKE_CASE							:




      def __init__(	self			, lowerCamelCase			, lowerCamelCase   )				->List[Any]:



         '''simple docstring'''
         __a					  =     BreadthFirstSearch(SCREAMING_SNAKE_CASE_			, SCREAMING_SNAKE_CASE_   )
         __a					  =     BreadthFirstSearch(SCREAMING_SNAKE_CASE_			, SCREAMING_SNAKE_CASE_   )
         __a					  =     False




      def 			__UpperCamelCase				(	self   )				->List[str]:



         '''simple docstring'''




         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
            __a					  =     self.fwd_bfs.node_queue.pop(0   )
            __a					  =     self.bwd_bfs.node_queue.pop(0   )

            if current_bwd_node.pos == current_fwd_node.pos:
               __a					  =     True
               return self.retrace_bidirectional_path(
                   SCREAMING_SNAKE_CASE_			, SCREAMING_SNAKE_CASE_   )

            __a					  =     current_bwd_node
            __a					  =     current_fwd_node

            __a					  =     {
                self.fwd_bfs: self.fwd_bfs.get_successors(SCREAMING_SNAKE_CASE_   ),
                self.bwd_bfs: self.bwd_bfs.get_successors(SCREAMING_SNAKE_CASE_   ),
            }

            for bfs in [self.fwd_bfs, self.bwd_bfs]:
               for node in successors[bfs]:
                  bfs.node_queue.append(SCREAMING_SNAKE_CASE_   )

         if not self.reached:
            return [self.fwd_bfs.start.pos]
         return None






      def 			__UpperCamelCase				(	self			, lowerCamelCase			, lowerCamelCase   )				->Optional[Any]:



         '''simple docstring'''
         __a					  =     self.fwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_   )
         __a					  =     self.bwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_   )
         bwd_path.pop()
         bwd_path.reverse()
         __a					  =     fwd_path + bwd_path
         return path


if __name__ == "__main__":
 # all coordinates are given in format [y,x]
 import doctest

 doctest.testmod()
 __UpperCamelCase   :							Optional[Any]         =   (0, 0)
 __UpperCamelCase   :							Tuple         =   (len(grid) - 1, len(grid[0]) - 1)
 for elem in grid:
  print(elem)

 __UpperCamelCase   :							Tuple         =   time.time()
 __UpperCamelCase   :							Union[str, Any]         =   BreadthFirstSearch(init, goal)
 __UpperCamelCase   :							List[Any]         =   bfs.search()
 __UpperCamelCase   :							str         =   time.time() - start_bfs_time

 print("""Unidirectional BFS computation time : """, bfs_time)

 __UpperCamelCase   :							Tuple         =   time.time()
 __UpperCamelCase   :							Union[str, Any]         =   BidirectionalBreadthFirstSearch(init, goal)
 __UpperCamelCase   :							Union[str, Any]         =   bd_bfs.search()
 __UpperCamelCase   :							Optional[Any]         =   time.time() - start_bd_bfs_time

 print("""Bidirectional BFS computation time : """, bd_bfs_time)

def 		UpperCamelCase						(   lowercase_ )		->						int:


  '''simple docstring'''






  if n == 1 or not isinstance(lowercase_			,			lowercase_ ):
    return 0
  elif n == 2:
    return 1
  else:
    lowercase__	: List[Any]     		=   [0, 1]
    for i in range(2			,			n + 1 ):
      sequence.append(sequence[i - 1] + sequence[i - 2] )

    return sequence[n]

def 		UpperCamelCase						(   lowercase_ )		->						int:


  '''simple docstring'''






  lowercase__	: Optional[Any]     		=   0
  lowercase__	: Dict     		=   2

  while digits < n:
    index += 1
    lowercase__	: str     		=   len(str(fibonacci(lowercase_ ) ) )

  return index

def 		UpperCamelCase						(   lowercase_ = 10_00 )		->						int:


  '''simple docstring'''






  return fibonacci_digits_index(lowercase_ )


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






