


"""simple docstring"""






from __future__ import annotations

import time

__snake_case		=       list[tuple[int, int]]

__snake_case		=       [
    [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],
]

__snake_case		=       [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class     __lowerCamelCase  :

     '''simple docstring'''


     def __init__(      self    ,				__UpperCAmelCase    ,				__UpperCAmelCase    ,				__UpperCAmelCase    ,				__UpperCAmelCase    ,				__UpperCAmelCase							)       ->							List[str]:
          _a    	=				pos_x
          _a    	=				pos_y
          _a    	=				(pos_y, pos_x)
          _a    	=				goal_x
          _a    	=				goal_y
          _a    	=				parent







class     __lowerCamelCase  :

     '''simple docstring'''


     def __init__(      self    ,				__UpperCAmelCase    ,				__UpperCAmelCase							)       ->							List[str]:
          _a    	=				Node(start[1]    ,				start[0]    ,				goal[1]    ,				goal[0]    ,				__UpperCAmelCase							)
          _a    	=				Node(goal[1]    ,				goal[0]    ,				goal[1]    ,				goal[0]    ,				__UpperCAmelCase							)

          _a    	=				[self.start]
          _a    	=				False


     def 							_UpperCAmelCase      (      self							)       ->							Path | None:
          while self.node_queue:
               _a    	=				self.node_queue.pop(0							)

               if current_node.pos == self.target.pos:
                    _a    	=				True
                    return self.retrace_path(__UpperCAmelCase							)

               _a    	=				self.get_successors(__UpperCAmelCase							)

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

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


     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							list[Node]:
          _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(__UpperCAmelCase							) - 1):
                    continue

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

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





     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase							)       ->							Path:
          _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     __lowerCamelCase  :

     '''simple docstring'''


     def __init__(      self    ,				__UpperCAmelCase    ,				__UpperCAmelCase							)       ->							Tuple:
          _a    	=				BreadthFirstSearch(__UpperCAmelCase    ,				__UpperCAmelCase							)
          _a    	=				BreadthFirstSearch(__UpperCAmelCase    ,				__UpperCAmelCase							)
          _a    	=				False


     def 							_UpperCAmelCase      (      self							)       ->							Path | None:
          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(
                        __UpperCAmelCase    ,				__UpperCAmelCase							)

               _a    	=				current_bwd_node
               _a    	=				current_fwd_node

               _a    	=				{
                   self.fwd_bfs: self.fwd_bfs.get_successors(__UpperCAmelCase							),
                   self.bwd_bfs: self.bwd_bfs.get_successors(__UpperCAmelCase							),
               }

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

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





     def 							_UpperCAmelCase      (      self    ,				__UpperCAmelCase    ,				__UpperCAmelCase							)       ->							Path:
          _a    	=				self.fwd_bfs.retrace_path(__UpperCAmelCase							)
          _a    	=				self.bwd_bfs.retrace_path(__UpperCAmelCase							)
          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()
   __snake_case		=       (0, 0)
   __snake_case		=       (len(grid) - 1, len(grid[0]) - 1)
   for elem in grid:
      print(elem)

   __snake_case		=       time.time()
   __snake_case		=       BreadthFirstSearch(init, goal)
   __snake_case		=       bfs.search()
   __snake_case		=       time.time() - start_bfs_time

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

   __snake_case		=       time.time()
   __snake_case		=       BidirectionalBreadthFirstSearch(init, goal)
   __snake_case		=       bd_bfs.search()
   __snake_case		=       time.time() - start_bd_bfs_time

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



"""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())))