from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

_UpperCAmelCase            =		TypeVar("""T""")




def     UpperCamelCase						(	__lowercase						:			int     ):
		'''simple docstring'''




		return (position - 1) // 2




def     UpperCamelCase						(	__lowercase						:			int     ):
		'''simple docstring'''




		return (2 * position) + 1




def     UpperCamelCase						(	__lowercase						:			int     ):
		'''simple docstring'''




		return (2 * position) + 2





class UpperCAmelCase						( Generic[T]  ):


				'''simple docstring'''






				def __init__(						self ):



						"""simple docstring"""





						A_		:    list[tuple[T, int]]         =				[]
						A_		:    dict[T, int]         =				{}
						A_		:    int         =				0
				def __len__(						self ):



						"""simple docstring"""





						return self.elements
				def __repr__(						self ):



						"""simple docstring"""





						return str(self.heap )
				def   lowerCAmelCase_       (						self ):



						"""simple docstring"""





						return self.elements == 0
				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase ):



						"""simple docstring"""





						self.heap.append((elem, weight) )
						A_		:    Optional[Any]         =				self.elements
						self.elements += 1
						self._bubble_up(lowercase )
				def   lowerCAmelCase_       (						self ):



						"""simple docstring"""





						if self.elements > 1:
								self._swap_nodes(0		,     self.elements - 1 )
						A_       ,      A_		:    Union[str, Any]         =				self.heap.pop()
						del self.position_map[elem]
						self.elements -= 1
						if self.elements > 0:
								A_       ,      A_		:    Dict         =				self.heap[0]
								self._bubble_down(lowercase )
						return elem
				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase ):



						"""simple docstring"""





						A_		:    List[str]         =				self.position_map[elem]
						A_		:    List[Any]         =				(elem, weight)
						if position > 0:
								A_		:    Dict         =				get_parent_position(lowercase )
								A_       ,      A_		:    Optional[int]         =				self.heap[parent_position]
								if parent_weight > weight:
										self._bubble_up(lowercase )
								else:
										self._bubble_down(lowercase )
						else:
								self._bubble_down(lowercase )
				def   lowerCAmelCase_       (						self		,     lowercase ):



						"""simple docstring"""





						A_		:    Union[str, Any]         =				self.position_map[elem]
						if curr_pos == 0:
								return None
						A_		:    Dict         =				get_parent_position(lowercase )
						A_       ,      A_		:    Optional[int]         =				self.heap[curr_pos]
						A_       ,      A_		:    Tuple         =				self.heap[parent_position]
						if parent_weight > weight:
								self._swap_nodes(lowercase		,     lowercase )
								return self._bubble_up(lowercase )
						return None
				def   lowerCAmelCase_       (						self		,     lowercase ):



						"""simple docstring"""





						A_		:    List[Any]         =				self.position_map[elem]
						A_       ,      A_		:    List[str]         =				self.heap[curr_pos]
						A_		:    int         =				get_child_left_position(lowercase )
						A_		:    Tuple         =				get_child_right_position(lowercase )
						if child_left_position < self.elements and child_right_position < self.elements:
								A_       ,      A_		:    str         =				self.heap[child_left_position]
								A_       ,      A_		:    int         =				self.heap[child_right_position]
								if child_right_weight < child_left_weight and child_right_weight < weight:
										self._swap_nodes(lowercase		,     lowercase )
										return self._bubble_down(lowercase )
						if child_left_position < self.elements:
								A_       ,      A_		:    Tuple         =				self.heap[child_left_position]
								if child_left_weight < weight:
										self._swap_nodes(lowercase		,     lowercase )
										return self._bubble_down(lowercase )
						else:
								return None
						if child_right_position < self.elements:
								A_       ,      A_		:    List[str]         =				self.heap[child_right_position]
								if child_right_weight < weight:
										self._swap_nodes(lowercase		,     lowercase )
										return self._bubble_down(lowercase )
						return None







				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase ):



						"""simple docstring"""





						A_		:    str         =				self.heap[nodea_pos][0]
						A_		:    Optional[int]         =				self.heap[nodea_pos][0]
						A_       ,      A_		:    Dict         =				(
						    self.heap[nodea_pos],
						    self.heap[nodea_pos],
						)
						A_		:    str         =				nodea_pos
						A_		:    Dict         =				nodea_pos





class UpperCAmelCase						( Generic[T]  ):


				'''simple docstring'''






				def __init__(						self ):



						"""simple docstring"""





						A_		:    dict[T, dict[T, int]]         =				{}
						A_		:    int         =				0
				def __repr__(						self ):



						"""simple docstring"""





						return str(self.connections )
				def __len__(						self ):



						"""simple docstring"""





						return self.nodes
				def   lowerCAmelCase_       (						self		,     lowercase ):



						"""simple docstring"""





						if node not in self.connections:
								A_		:    int         =				{}
								self.nodes += 1







				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase		,     lowercase ):



						"""simple docstring"""





						self.add_node(lowercase )
						self.add_node(lowercase )
						A_		:    Any         =				weight
						A_		:    List[Any]         =				weight




def     UpperCamelCase						(	__lowercase						:			GraphUndirectedWeighted[T]						,):
		'''simple docstring'''




		A_		:    dict[T, int]         =				{node: maxsize for node in graph.connections}
		A_		:    dict[T, T | None]         =				{node: None for node in graph.connections}

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

		if priority_queue.is_empty():
				return dist, parent

		# initialization
		A_		:    Optional[int]         =				priority_queue.extract_min()
		A_		:    Dict         =				0
		for neighbour in graph.connections[node]:
				if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
						A_		:    Optional[int]         =				dist[node] + graph.connections[node][neighbour]
						priority_queue.update_key(__lowercase						,dist[neighbour]     )
						A_		:    Dict         =				node

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







from math import isqrt




def     UpperCamelCase						(	__lowercase						:			int     ):
		'''simple docstring'''




		return all(number % divisor != 0 for divisor in range(2						,isqrt(__lowercase     ) + 1     )     )




def     UpperCamelCase						(	__lowercase						:			int = 10**6     ):
		'''simple docstring'''




		A_		:    Optional[Any]         =				0
		A_		:    List[str]         =				1
		A_		:    Dict         =				7
		while prime_candidate < max_prime:
				primes_count += is_prime(__lowercase     )

				cube_index += 1
				prime_candidate += 6 * cube_index

		return primes_count


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






