


'''simple docstring'''



from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

A__						:   Optional[Any]				=    TypeVar("""T""")



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int				)	->						int:
     return (position - 1) // 2



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int				)	->						int:
     return (2 * position) + 1



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int				)	->						int:
     return (2 * position) + 2





class   UpperCAmelCase_    (Generic[T]    ):





    """simple docstring"""






    def __init__(				self      )							->	None:
         __lowerCamelCase  :      list[tuple[T, int]]														=						[]
         __lowerCamelCase  :      dict[T, int]														=						{}
         __lowerCamelCase  :      int														=						0







    def __len__(				self      )							->	int:
         return self.elements







    def __repr__(				self      )							->	str:
         return str(self.heap      )







    def  lowercase_							(				self      )							->	bool:
         # Check if the priority queue is empty
         return self.elements == 0







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Add an element with given priority to the queue
         self.heap.append((elem, weight)      )
         __lowerCamelCase  :      Any														=						self.elements
         self.elements += 1
         self._bubble_up(SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self      )							->	T:
         # Remove and return the element with lowest weight (highest priority)
         if self.elements > 1:
              self._swap_nodes(0     ,	self.elements - 1      )
         __lowerCamelCase							,			__lowerCamelCase  :      int														=						self.heap.pop()
         del self.position_map[elem]
         self.elements -= 1
         if self.elements > 0:
              __lowerCamelCase							,			__lowerCamelCase  :      Optional[int]														=						self.heap[0]
              self._bubble_down(SCREAMING_SNAKE_CASE_      )
         return elem







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Update the weight of the given key
         __lowerCamelCase  :      Union[str, Any]														=						self.position_map[elem]
         __lowerCamelCase  :      Any														=						(elem, weight)
         if position > 0:
              __lowerCamelCase  :      Union[str, Any]														=						get_parent_position(SCREAMING_SNAKE_CASE_      )
              __lowerCamelCase							,			__lowerCamelCase  :      List[str]														=						self.heap[parent_position]
              if parent_weight > weight:
                   self._bubble_up(SCREAMING_SNAKE_CASE_      )
              else:
                   self._bubble_down(SCREAMING_SNAKE_CASE_      )
         else:
              self._bubble_down(SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Place a node at the proper position (upward movement) [to be used internally
         # only]
         __lowerCamelCase  :      Tuple														=						self.position_map[elem]
         if curr_pos == 0:
              return None
         __lowerCamelCase  :      Dict														=						get_parent_position(SCREAMING_SNAKE_CASE_      )
         __lowerCamelCase							,			__lowerCamelCase  :      int														=						self.heap[curr_pos]
         __lowerCamelCase							,			__lowerCamelCase  :      Union[str, Any]														=						self.heap[parent_position]
         if parent_weight > weight:
              self._swap_nodes(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
              return self._bubble_up(SCREAMING_SNAKE_CASE_      )
         return None







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Place a node at the proper position (downward movement) [to be used
         # internally only]
         __lowerCamelCase  :      List[str]														=						self.position_map[elem]
         __lowerCamelCase							,			__lowerCamelCase  :      int														=						self.heap[curr_pos]
         __lowerCamelCase  :      Union[str, Any]														=						get_child_left_position(SCREAMING_SNAKE_CASE_      )
         __lowerCamelCase  :      List[Any]														=						get_child_right_position(SCREAMING_SNAKE_CASE_      )
         if child_left_position < self.elements and child_right_position < self.elements:
              __lowerCamelCase							,			__lowerCamelCase  :      Dict														=						self.heap[child_left_position]
              __lowerCamelCase							,			__lowerCamelCase  :      List[Any]														=						self.heap[child_right_position]
              if child_right_weight < child_left_weight and child_right_weight < weight:
                   self._swap_nodes(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
                   return self._bubble_down(SCREAMING_SNAKE_CASE_      )
         if child_left_position < self.elements:
              __lowerCamelCase							,			__lowerCamelCase  :      Optional[int]														=						self.heap[child_left_position]
              if child_left_weight < weight:
                   self._swap_nodes(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
                   return self._bubble_down(SCREAMING_SNAKE_CASE_      )
         else:
              return None
         if child_right_position < self.elements:
              __lowerCamelCase							,			__lowerCamelCase  :      List[str]														=						self.heap[child_right_position]
              if child_right_weight < weight:
                   self._swap_nodes(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
                   return self._bubble_down(SCREAMING_SNAKE_CASE_      )
         return None







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Swap the nodes at the given positions
         __lowerCamelCase  :      List[Any]														=						self.heap[nodea_pos][0]
         __lowerCamelCase  :      Tuple														=						self.heap[nodea_pos][0]
         __lowerCamelCase							,			__lowerCamelCase  :      Optional[Any]														=						(
             self.heap[nodea_pos],
             self.heap[nodea_pos],
         )
         __lowerCamelCase  :      int														=						nodea_pos
         __lowerCamelCase  :      Optional[Any]														=						nodea_pos







class   UpperCAmelCase_    (Generic[T]    ):





    """simple docstring"""






    def __init__(				self      )							->	None:
         __lowerCamelCase  :      dict[T, dict[T, int]]														=						{}
         __lowerCamelCase  :      int														=						0







    def __repr__(				self      )							->	str:
         return str(self.connections      )







    def __len__(				self      )							->	int:
         return self.nodes







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Add a node in the graph if it is not in the graph
         if node not in self.connections:
              __lowerCamelCase  :      Optional[Any]														=						{}
              self.nodes += 1







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	None:
         # Add an edge between 2 nodes in the graph
         self.add_node(SCREAMING_SNAKE_CASE_      )
         self.add_node(SCREAMING_SNAKE_CASE_      )
         __lowerCamelCase  :      int														=						weight
         __lowerCamelCase  :      Dict														=						weight







def      UpperCAmelCase__   (      UpperCAmelCase_       :							GraphUndirectedWeighted[T] ,       )	->						tuple[dict[T, int], dict[T, T | None]]:
     __lowerCamelCase  :      dict[T, int]														=						{node: maxsize for node in graph.connections}
     __lowerCamelCase  :      dict[T, T | None]														=						{node: None for node in graph.connections}

     __lowerCamelCase  :      MinPriorityQueue[T]														=						MinPriorityQueue()
     for node, weight in dist.items():
          priority_queue.push(UpperCAmelCase_ ,       UpperCAmelCase_				)

     if priority_queue.is_empty():
          return dist, parent

     # initialization
     __lowerCamelCase  :      List[Any]														=						priority_queue.extract_min()
     __lowerCamelCase  :      Union[str, Any]														=						0
     for neighbour in graph.connections[node]:
          if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
               __lowerCamelCase  :      int														=						dist[node] + graph.connections[node][neighbour]
               priority_queue.update_key(UpperCAmelCase_ ,       dist[neighbour]				)
               __lowerCamelCase  :      int														=						node

    # running prim's algorithm
     while not priority_queue.is_empty():
          __lowerCamelCase  :      List[Any]														=						priority_queue.extract_min()
          for neighbour in graph.connections[node]:
               if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
                    __lowerCamelCase  :      int														=						dist[node] + graph.connections[node][neighbour]
                    priority_queue.update_key(UpperCAmelCase_ ,       dist[neighbour]				)
                    __lowerCamelCase  :      Union[str, Any]														=						node
     return dist, parent










'''simple docstring'''



from collections import defaultdict
from math import gcd



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int = 1_50_00_00				)	->						int:
     __lowerCamelCase  :      defaultdict														=						defaultdict(UpperCAmelCase_				)
     __lowerCamelCase  :      Any														=						2
     while 2 * euclid_m * (euclid_m + 1) <= limit:
          for euclid_n in range((euclid_m % 2) + 1 ,       UpperCAmelCase_ ,       2				):
               if gcd(UpperCAmelCase_ ,       UpperCAmelCase_				) > 1:
                    continue
               __lowerCamelCase  :      Any														=						2 * euclid_m * (euclid_m + euclid_n)
               for perimeter in range(UpperCAmelCase_ ,       limit + 1 ,       UpperCAmelCase_				):
                    frequencies[perimeter] += 1
          euclid_m += 1
     return sum(1 for frequency in frequencies.values() if frequency == 1				)


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






