





'''simple docstring'''



from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt




def    _lowerCAmelCase						(				lowerCamelCase_			:  int				):
			__lowercase										=							int(number**0.5				)
			return number == sq * sq




def    _lowerCAmelCase						(				lowerCamelCase_			:  int		,       lowerCamelCase_			:  int		,       lowerCamelCase_			:  int		,       lowerCamelCase_			:  int		,       lowerCamelCase_			:  int		,       lowerCamelCase_			:  int				):
			__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(lowerCamelCase_		,       lowerCamelCase_				)
			top //= hcf
			bottom //= hcf
			return top, bottom




def    _lowerCAmelCase						(				lowerCamelCase_			:  int = 3_5				):
			__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(lowerCamelCase_		,       lowerCamelCase_				)
															z_num //= hcf
															z_den //= hcf
															if 0 < z_num < z_den <= order:
																		__lowercase										=							add_three(
																		    lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_				)
																		unique_s.add(lowerCamelCase_				)

															# 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(lowerCamelCase_				) and is_sq(lowerCamelCase_				):
																		__lowercase										=							int(sqrt(lowerCamelCase_				)				)
																		__lowercase										=							int(sqrt(lowerCamelCase_				)				)
																		__lowercase										=							gcd(lowerCamelCase_		,       lowerCamelCase_				)
																		z_num //= hcf
																		z_den //= hcf
																		if 0 < z_num < z_den <= order:
																					__lowercase										=							add_three(
																					    lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_				)
																					unique_s.add(lowerCamelCase_				)

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

															# 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(lowerCamelCase_				) and is_sq(lowerCamelCase_				):
																		__lowercase										=							int(sqrt(lowerCamelCase_				)				)
																		__lowercase										=							int(sqrt(lowerCamelCase_				)				)
																		__lowercase										=							gcd(lowerCamelCase_		,       lowerCamelCase_				)
																		z_num //= hcf
																		z_den //= hcf
																		if 0 < z_num < z_den <= order:
																					__lowercase										=							add_three(
																					    lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_				)
																					unique_s.add(lowerCamelCase_				)

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

			return total.denominator + total.numerator


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












'''simple docstring'''



from __future__ import annotations

from typing import Any






class 							__lowercase       :







	'''simple docstring'''

	def __init__(self     ,_lowerCamelCase )							->							None:







				'''simple docstring'''





				__lowercase										=							num_of_nodes
				__lowercase										=							[]
				__lowercase										=							{}


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase     ,_lowerCamelCase     ,_lowerCamelCase )							->							None:







				'''simple docstring'''





				self.m_edges.append([u_node, v_node, weight] )


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase )							->							int:







				'''simple docstring'''





				if self.m_component[u_node] == u_node:
							return u_node
				return self.find_component(self.m_component[u_node] )


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase )							->							None:







				'''simple docstring'''





				if self.m_component[u_node] != u_node:
							for k in self.m_component:
										__lowercase										=							self.find_component(_lowerCamelCase )


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase     ,_lowerCamelCase     ,_lowerCamelCase )							->							None:







				'''simple docstring'''





				if component_size[u_node] <= component_size[v_node]:
							__lowercase										=							v_node
							component_size[v_node] += component_size[u_node]
							self.set_component(_lowerCamelCase )

				elif component_size[u_node] >= component_size[v_node]:
							__lowercase										=							self.find_component(_lowerCamelCase )
							component_size[u_node] += component_size[v_node]
							self.set_component(_lowerCamelCase )


	def 						_UpperCAmelCase     (self )							->							None:







				'''simple docstring'''





				__lowercase										=							[]
				__lowercase										=							0

				__lowercase										=							[-1] * self.m_num_of_nodes

				# A list of components (initialized to all of the nodes)
				for node in range(self.m_num_of_nodes ):
							self.m_component.update({node: node} )
							component_size.append(1 )

				__lowercase										=							self.m_num_of_nodes

				while num_of_components > 1:
							for edge in self.m_edges:
										__lowercase						,		__lowercase						,		__lowercase										=							edge

										__lowercase										=							self.m_component[u]
										__lowercase										=							self.m_component[v]

										if u_component != v_component:

													for component in (u_component, v_component):
																if (
																    minimum_weight_edge[component] == -1
																    or minimum_weight_edge[component][2] > w
																):
																			__lowercase										=							[u, v, w]

							for edge in minimum_weight_edge:
										if isinstance(_lowerCamelCase     ,_lowerCamelCase ):
													__lowercase						,		__lowercase						,		__lowercase										=							edge

													__lowercase										=							self.m_component[u]
													__lowercase										=							self.m_component[v]

													if u_component != v_component:
																mst_weight += w
																self.union(_lowerCamelCase     ,_lowerCamelCase     ,_lowerCamelCase )
																print(f"Added edge [{u} - {v}]\nAdded weight: {w}\n" )
																num_of_components -= 1

							__lowercase										=							[-1] * self.m_num_of_nodes
				print(f"The total weight of the minimal spanning tree is: {mst_weight}" )





def    _lowerCAmelCase						(				):
			pass


if __name__ == "__main__":
	import doctest

	doctest.testmod()





