from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

A_      =      TypeVar("T")






def        __UpperCAmelCase    (       UpperCAmelCase       )->       List[Any]:



			"""simple docstring"""







			return (position - 1) // 2






def        __UpperCAmelCase    (       UpperCAmelCase       )->       List[str]:



			"""simple docstring"""







			return (2 * position) + 1






def        __UpperCAmelCase    (       UpperCAmelCase       )->       Dict:



			"""simple docstring"""







			return (2 * position) + 2
class      __lowercase					(    Generic[T]    ):

						def __init__(	self				:      int   )							->		None:


									'''simple docstring'''

									lowercase							=		[]
									lowercase							=		{}
									lowercase							=		0

						def __len__(	self				:      Optional[int]   )							->		int:


									'''simple docstring'''

									return self.elements

						def __repr__(	self				:      str   )							->		str:


									'''simple docstring'''

									return str(self.heap   )

						def        __a		(	self				:      Optional[Any]   )							->		bool:


									'''simple docstring'''

									return self.elements == 0

						def        __a		(	self				:      List[str]							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      int   )							->		None:


									'''simple docstring'''

									self.heap.append((elem, weight)   )
									lowercase							=		self.elements
									self.elements += 1
									self._bubble_up(_UpperCAmelCase   )

						def        __a		(	self				:      int   )							->		T:


									'''simple docstring'''

									if self.elements > 1:
												self._swap_nodes(0							,							self.elements - 1   )
									lowercase		,lowercase							=		self.heap.pop()
									del self.position_map[elem]
									self.elements -= 1
									if self.elements > 0:
												lowercase		,lowercase							=		self.heap[0]
												self._bubble_down(_UpperCAmelCase   )
									return elem

						def        __a		(	self				:      Dict							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      int   )							->		None:


									'''simple docstring'''

									lowercase							=		self.position_map[elem]
									lowercase							=		(elem, weight)
									if position > 0:
												lowercase							=		get_parent_position(_UpperCAmelCase   )
												lowercase		,lowercase							=		self.heap[parent_position]
												if parent_weight > weight:
															self._bubble_up(_UpperCAmelCase   )
												else:
															self._bubble_down(_UpperCAmelCase   )
									else:
												self._bubble_down(_UpperCAmelCase   )

						def        __a		(	self				:      Union[str, Any]							,							__lowerCamelCase				:      T   )							->		None:


									'''simple docstring'''

									lowercase							=		self.position_map[elem]
									if curr_pos == 0:
												return None
									lowercase							=		get_parent_position(_UpperCAmelCase   )
									lowercase		,lowercase							=		self.heap[curr_pos]
									lowercase		,lowercase							=		self.heap[parent_position]
									if parent_weight > weight:
												self._swap_nodes(_UpperCAmelCase							,							_UpperCAmelCase   )
												return self._bubble_up(_UpperCAmelCase   )
									return None

						def        __a		(	self				:      Any							,							__lowerCamelCase				:      T   )							->		None:


									'''simple docstring'''

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



						def        __a		(	self				:      Tuple							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      int   )							->		None:


									'''simple docstring'''

									lowercase							=		self.heap[nodea_pos][0]
									lowercase							=		self.heap[nodea_pos][0]
									lowercase		,lowercase							=		(
									    self.heap[nodea_pos],
									    self.heap[nodea_pos],
									)
									lowercase							=		nodea_pos
									lowercase							=		nodea_pos





class      __lowercase					(    Generic[T]    ):

						def __init__(	self				:      Any   )							->		None:


									'''simple docstring'''

									lowercase							=		{}
									lowercase							=		0

						def __repr__(	self				:      List[str]   )							->		str:


									'''simple docstring'''

									return str(self.connections   )

						def __len__(	self				:      Optional[Any]   )							->		int:


									'''simple docstring'''

									return self.nodes

						def        __a		(	self				:      int							,							__lowerCamelCase				:      T   )							->		None:


									'''simple docstring'''

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



						def        __a		(	self				:      int							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      int   )							->		None:


									'''simple docstring'''

									self.add_node(_UpperCAmelCase   )
									self.add_node(_UpperCAmelCase   )
									lowercase							=		weight
									lowercase							=		weight






def        __UpperCAmelCase    (       UpperCAmelCase,		)->       Union[str, Any]:



			"""simple docstring"""







			lowercase							=		{node: maxsize for node in graph.connections}
			lowercase							=		{node: None for node in graph.connections}

			lowercase							=		MinPriorityQueue()
			for node, weight in dist.items():
						priority_queue.push(lowerCAmelCase__,		lowerCAmelCase__       )

			if priority_queue.is_empty():
						return dist, parent

			# initialization
			lowercase							=		priority_queue.extract_min()
			lowercase							=		0
			for neighbour in graph.connections[node]:
						if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
									lowercase							=		dist[node] + graph.connections[node][neighbour]
									priority_queue.update_key(lowerCAmelCase__,		dist[neighbour]       )
									lowercase							=		node

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






from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt






def        __UpperCAmelCase    (       UpperCAmelCase       )->       bool:



			"""simple docstring"""







			lowercase							=		int(number**0.5       )
			return number == sq * sq






def        __UpperCAmelCase    (       UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase       )->       tuple[int, int]:



			"""simple docstring"""







			lowercase							=		x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
			lowercase							=		x_den * y_den * z_den
			lowercase							=		gcd(UpperCAmelCase,		UpperCAmelCase       )
			top //= hcf
			bottom //= hcf
			return top, bottom






def        __UpperCAmelCase    (       UpperCAmelCase = 35       )->       int:



			"""simple docstring"""







			lowercase							=		set()
			lowercase							=		42
			lowercase							=		Fraction(0       )
			lowercase							=		42

			for x_num in range(1,		order + 1       ):
						for x_den in range(x_num + 1,		order + 1       ):
									for y_num in range(1,		order + 1       ):
												for y_den in range(y_num + 1,		order + 1       ):
															# n=1
															lowercase							=		x_num * y_den + x_den * y_num
															lowercase							=		x_den * y_den
															lowercase							=		gcd(UpperCAmelCase,		UpperCAmelCase       )
															z_num //= hcf
															z_den //= hcf
															if 0 < z_num < z_den <= order:
																		lowercase							=		add_three(
																		    UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase       )
																		unique_s.add(UpperCAmelCase       )

															# n=2
															lowercase							=		(
															    x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
															)
															lowercase							=		x_den * x_den * y_den * y_den
															if is_sq(UpperCAmelCase       ) and is_sq(UpperCAmelCase       ):
																		lowercase							=		int(sqrt(UpperCAmelCase       )       )
																		lowercase							=		int(sqrt(UpperCAmelCase       )       )
																		lowercase							=		gcd(UpperCAmelCase,		UpperCAmelCase       )
																		z_num //= hcf
																		z_den //= hcf
																		if 0 < z_num < z_den <= order:
																					lowercase							=		add_three(
																					    UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase       )
																					unique_s.add(UpperCAmelCase       )

                    # n=-1
															lowercase							=		x_num * y_num
															lowercase							=		x_den * y_num + x_num * y_den
															lowercase							=		gcd(UpperCAmelCase,		UpperCAmelCase       )
															z_num //= hcf
															z_den //= hcf
															if 0 < z_num < z_den <= order:
																		lowercase							=		add_three(
																		    UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase       )
																		unique_s.add(UpperCAmelCase       )

															# n=2
															lowercase							=		x_num * x_num * y_num * y_num
															lowercase							=		(
															    x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
															)
															if is_sq(UpperCAmelCase       ) and is_sq(UpperCAmelCase       ):
																		lowercase							=		int(sqrt(UpperCAmelCase       )       )
																		lowercase							=		int(sqrt(UpperCAmelCase       )       )
																		lowercase							=		gcd(UpperCAmelCase,		UpperCAmelCase       )
																		z_num //= hcf
																		z_den //= hcf
																		if 0 < z_num < z_den <= order:
																					lowercase							=		add_three(
																					    UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase,		UpperCAmelCase       )
																					unique_s.add(UpperCAmelCase       )

			for num, den in unique_s:
						total += Fraction(UpperCAmelCase,		UpperCAmelCase       )

			return total.denominator + total.numerator


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





