





from __future__ import annotations

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






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:list[list[int]]   ,   SCREAMING_SNAKE_CASE		:list[int]   ,   SCREAMING_SNAKE_CASE		:list[int]   ,   SCREAMING_SNAKE_CASE		:int   ,   SCREAMING_SNAKE_CASE		:list[list[int]]   ,   )      ->   tuple[list[list[int]], list[list[int]]]:
 __lowerCAmelCase					:	Any      =       [
     [0 for col in range(len(grid[0]   )   )] for row in range(len(SCREAMING_SNAKE_CASE   )   )
 ]  # the reference grid
 __lowerCAmelCase					:	Optional[Any]      =       1
 __lowerCAmelCase					:	Any      =       [
     [0 for col in range(len(grid[0]   )   )] for row in range(len(SCREAMING_SNAKE_CASE   )   )
 ]  # the action grid

 __lowerCAmelCase					:	Dict      =       init[0]
 __lowerCAmelCase					:	Dict      =       init[1]
 __lowerCAmelCase					:	List[Any]      =       0
 __lowerCAmelCase					:	int      =       g + heuristic[x][y]  # cost from starting cell to destination cell
 __lowerCAmelCase					:	int      =       [[f, g, x, y]]

 __lowerCAmelCase					:	List[str]      =       False  # flag that is set when search is complete
 __lowerCAmelCase					:	Tuple      =       False  # flag set if we can't find expand

 while not found and not resign:
  if len(SCREAMING_SNAKE_CASE   ) == 0:
   raise ValueError("""Algorithm is unable to find solution"""   )
  else:  # to choose the least costliest action so as to move closer to the goal
   cell.sort()
   cell.reverse()
   __lowerCAmelCase					:	Optional[Any]      =       cell.pop()
   __lowerCAmelCase					:	str      =       next_cell[2]
   __lowerCAmelCase					:	List[Any]      =       next_cell[3]
   __lowerCAmelCase					:	Any      =       next_cell[1]

   if x == goal[0] and y == goal[1]:
    __lowerCAmelCase					:	Dict      =       True
   else:
    for i in range(len(SCREAMING_SNAKE_CASE   )   ):  # to try out different valid actions
     __lowerCAmelCase					:	Union[str, Any]      =       x + DIRECTIONS[i][0]
     __lowerCAmelCase					:	Tuple      =       y + DIRECTIONS[i][1]
     if xa >= 0 and xa < len(SCREAMING_SNAKE_CASE   ) and ya >= 0 and ya < len(grid[0]   ):
      if closed[xa][ya] == 0 and grid[xa][ya] == 0:
       __lowerCAmelCase					:	Optional[int]      =       g + cost
       __lowerCAmelCase					:	int      =       ga + heuristic[xa][ya]
       cell.append([fa, ga, xa, ya]   )
       __lowerCAmelCase					:	Dict      =       1
       __lowerCAmelCase					:	int      =       i
 __lowerCAmelCase					:	Union[str, Any]      =       []
 __lowerCAmelCase					:	List[str]      =       goal[0]
 __lowerCAmelCase					:	Dict      =       goal[1]
 invpath.append([x, y]   )  # we get the reverse path from here
 while x != init[0] or y != init[1]:
  __lowerCAmelCase					:	List[str]      =       x - DIRECTIONS[action[x][y]][0]
  __lowerCAmelCase					:	Tuple      =       y - DIRECTIONS[action[x][y]][1]
  __lowerCAmelCase					:	Optional[int]      =       xa
  __lowerCAmelCase					:	List[Any]      =       ya
  invpath.append([x, y]   )

 __lowerCAmelCase					:	str      =       []
 for i in range(len(SCREAMING_SNAKE_CASE   )   ):
  path.append(invpath[len(SCREAMING_SNAKE_CASE   ) - 1 - i]   )
 return path, action


if __name__ == "__main__":
      _UpperCAmelCase             =							[
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 1, 0],
          [0, 0, 0, 0, 1, 0],
      ]

      _UpperCAmelCase             =							[0, 0]
      # all coordinates are given in format [y,x]
      _UpperCAmelCase             =							[len(grid) - 1, len(grid[0]) - 1]
      _UpperCAmelCase             =							1

      # the cost map which pushes the path closer to the goal
      _UpperCAmelCase             =							[[0 for row in range(len(grid[0]))] for col in range(len(grid))]
      for i in range(len(grid)):
            for j in range(len(grid[0])):
                  _UpperCAmelCase             =							abs(i - goal[0]) + abs(j - goal[1])
                  if grid[i][j] == 1:
                        # added extra penalty in the heuristic map
                        _UpperCAmelCase             =							99

      _UpperCAmelCase       ,     _UpperCAmelCase             =							search(grid, init, goal, cost, heuristic)

      print('ACTION MAP')
      for i in range(len(action)):
            print(action[i])

      for i in range(len(path)):
            print(path[i])






from math import isqrt






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:int   )      ->   list[int]:
 __lowerCAmelCase					:	Tuple      =       [True] * max_number
 for i in range(2   ,   isqrt(max_number - 1   ) + 1   ):
  if is_prime[i]:
   for j in range(i**2   ,   SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ):
    __lowerCAmelCase					:	Tuple      =       False

 return [i for i in range(2   ,   SCREAMING_SNAKE_CASE   ) if is_prime[i]]






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:int = 10**8   )      ->   int:
 __lowerCAmelCase					:	int      =       calculate_prime_numbers(max_number // 2   )

 __lowerCAmelCase					:	List[Any]      =       0
 __lowerCAmelCase					:	List[str]      =       0
 __lowerCAmelCase					:	List[Any]      =       len(SCREAMING_SNAKE_CASE   ) - 1
 while left <= right:
  while prime_numbers[left] * prime_numbers[right] >= max_number:
   right -= 1
  semiprimes_count += right - left + 1
  left += 1

 return semiprimes_count


if __name__ == "__main__":
      print(f'''{solution() = }''')