from __future__ import annotations

SCREAMING_SNAKE_CASE :	Any							     =		list[tuple[int, int]]

SCREAMING_SNAKE_CASE :	List[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],
]

SCREAMING_SNAKE_CASE :	int							     =		([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right
class    A_ :

  def __init__(		self :      Optional[Any]     ,							__SCREAMING_SNAKE_CASE :      int     ,							__SCREAMING_SNAKE_CASE :      int     ,							__SCREAMING_SNAKE_CASE :      int     ,							__SCREAMING_SNAKE_CASE :      int     ,							__SCREAMING_SNAKE_CASE :      float     ,							__SCREAMING_SNAKE_CASE :      Node | None     ,							):
   __a       =  pos_x
   __a       =  pos_y
   __a       =  (pos_y, pos_x)
   __a       =  goal_x
   __a       =  goal_y
   __a       =  g_cost
   __a       =  parent
   __a       =  self.calculate_heuristic()

  def 		_UpperCAmelCase   (		self :      Optional[int]       ):
   __a       =  abs(self.pos_x - self.goal_x       )
   __a       =  abs(self.pos_y - self.goal_y       )
   return dx + dy

  def __lt__(		self :      str     ,							__SCREAMING_SNAKE_CASE :      Optional[int]       ):
   return self.f_cost < other.f_cost
class    A_ :

  def __init__(		self :      Optional[Any]     ,							__SCREAMING_SNAKE_CASE :      tuple[int, int]     ,							__SCREAMING_SNAKE_CASE :      tuple[int, int]       ):
   __a       =  Node(start[1]     ,							start[0]     ,							goal[1]     ,							goal[0]     ,							0     ,							__SCREAMING_SNAKE_CASE       )
   __a       =  Node(goal[1]     ,							goal[0]     ,							goal[1]     ,							goal[0]     ,							9_99_99     ,							__SCREAMING_SNAKE_CASE       )

   __a       =  [self.start]
   __a       =  []

   __a       =  False

  def 		_UpperCAmelCase   (		self :      List[Any]       ):
   while self.open_nodes:
    # Open Nodes are sorted using __lt__
    self.open_nodes.sort()
    __a       =  self.open_nodes.pop(0       )

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

    self.closed_nodes.append(__SCREAMING_SNAKE_CASE       )
    __a       =  self.get_successors(__SCREAMING_SNAKE_CASE       )

    for child_node in successors:
     if child_node in self.closed_nodes:
      continue

     if child_node not in self.open_nodes:
      self.open_nodes.append(__SCREAMING_SNAKE_CASE       )
     else:
      # retrieve the best current path
      __a       =  self.open_nodes.pop(self.open_nodes.index(__SCREAMING_SNAKE_CASE       )       )

      if child_node.g_cost < better_node.g_cost:
       self.open_nodes.append(__SCREAMING_SNAKE_CASE       )
      else:
       self.open_nodes.append(__SCREAMING_SNAKE_CASE       )

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

  def 		_UpperCAmelCase   (		self :      List[str]     ,							__SCREAMING_SNAKE_CASE :      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(__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     ,							parent.g_cost + 1     ,							__SCREAMING_SNAKE_CASE     ,							)       )
   return successors

  def 		_UpperCAmelCase   (		self :      int     ,							__SCREAMING_SNAKE_CASE :      Node | None       ):
   __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


if __name__ == "__main__":
  SCREAMING_SNAKE_CASE :	Optional[Any]							     =		(0, 0)
  SCREAMING_SNAKE_CASE :	int							     =		(len(grid) - 1, len(grid[0]) - 1)
  for elem in grid:
    print(elem)

  print("""------""")

  SCREAMING_SNAKE_CASE :	List[Any]							     =		GreedyBestFirst(init, goal)
  SCREAMING_SNAKE_CASE :	str							     =		greedy_bf.search()
  if path:
    for pos_x, pos_y in path:
      SCREAMING_SNAKE_CASE :	Union[str, Any]							     =		2

    for elem in grid:
      print(elem)



def   __A		(			_A = 100_0000					):



 """simple docstring"""


 __a       =  [i - 1 for i in range(limit + 1					)]

 for i in range(2							,				limit + 1					):
  if phi[i] == i - 1:
   for j in range(2 * i							,				limit + 1							,				_A					):
    phi[j] -= phi[j] // i

 return sum(phi[2 : limit + 1]					)


if __name__ == "__main__":
  print(solution())


