



from __future__ import annotations

import math
import random
from typing import Any




class 							lowerCAmelCase__  :







					def __init__(       self      :     List[str]):
											A__	:							list[Any]						    = []
											A__	:							int						    = 0
											A__	:							int						    = 0







					def  _lowercase			(       self      :     Dict):
											return self.head == self.tail







					def  _lowercase			(       self      :     Any			,		_A      :     Any):
											self.data.append(_A)
											A__	:							Dict						    = self.tail + 1







					def  _lowercase			(       self      :     List[str]):
											A__	:							List[str]						    = self.data[self.head]
											A__	:							List[str]						    = self.head + 1
											return ret







					def  _lowercase			(       self      :     Optional[int]):
											return self.tail - self.head







					def  _lowercase			(       self      :     Union[str, Any]):
											print(self.data)
											print("**************")
											print(self.data[self.head : self.tail])




class 							lowerCAmelCase__  :







					def __init__(       self      :     str			,		_A      :     Any):
											A__	:							Union[str, Any]						    = data
											A__	:							MyNode | None						    = None
											A__	:							MyNode | None						    = None
											A__	:							int						    = 1







					def  _lowercase			(       self      :     int):
											return self.data







					def  _lowercase			(       self      :     str):
											return self.left







					def  _lowercase			(       self      :     str):
											return self.right







					def  _lowercase			(       self      :     List[str]):
											return self.height







					def  _lowercase			(       self      :     int			,		_A      :     Any):
											A__	:							Any						    = data







					def  _lowercase			(       self      :     str			,		_A      :     MyNode | None):
											A__	:							str						    = node







					def  _lowercase			(       self      :     Dict			,		_A      :     MyNode | None):
											A__	:							Optional[int]						    = node







					def  _lowercase			(       self      :     Optional[Any]			,		_A      :     int):
											A__	:							Any						    = height




def 	snake_case__       (					__lowercase       )		->		int:







						"""simple docstring"""

						if node is None:
												return 0
						return node.get_height()
def 	snake_case__       (					__lowercase							,     __lowercase       )		->		int:







						"""simple docstring"""

						if a > b:
												return a
						return b
def 	snake_case__       (					__lowercase       )		->		MyNode:







						"""simple docstring"""

						print("left rotation node:"							,     node.get_data()       )
						A__	:							int						    = node.get_left()
						assert ret is not None
						node.set_left(ret.get_right()       )
						ret.set_right(__lowercase       )
						A__	:							Tuple						    = my_max(get_height(node.get_right()       )							,     get_height(node.get_left()       )       ) + 1
						node.set_height(__lowercase       )
						A__	:							Union[str, Any]						    = my_max(get_height(ret.get_right()       )							,     get_height(ret.get_left()       )       ) + 1
						ret.set_height(__lowercase       )
						return ret
def 	snake_case__       (					__lowercase       )		->		MyNode:







						"""simple docstring"""

						print("right rotation node:"							,     node.get_data()       )
						A__	:							List[Any]						    = node.get_right()
						assert ret is not None
						node.set_right(ret.get_left()       )
						ret.set_left(__lowercase       )
						A__	:							Union[str, Any]						    = my_max(get_height(node.get_right()       )							,     get_height(node.get_left()       )       ) + 1
						node.set_height(__lowercase       )
						A__	:							int						    = my_max(get_height(ret.get_right()       )							,     get_height(ret.get_left()       )       ) + 1
						ret.set_height(__lowercase       )
						return ret
def 	snake_case__       (					__lowercase       )		->		MyNode:







						"""simple docstring"""

						A__	:							Tuple						    = node.get_left()
						assert left_child is not None
						node.set_left(left_rotation(__lowercase       )       )
						return right_rotation(__lowercase       )
def 	snake_case__       (					__lowercase       )		->		MyNode:







						"""simple docstring"""

						A__	:							int						    = node.get_right()
						assert right_child is not None
						node.set_right(right_rotation(__lowercase       )       )
						return left_rotation(__lowercase       )
def 	snake_case__       (					__lowercase							,     __lowercase       )		->		MyNode | None:







						"""simple docstring"""

						if node is None:
												return MyNode(__lowercase       )
						if data < node.get_data():
												node.set_left(insert_node(node.get_left()							,     __lowercase       )       )
												if (
												    get_height(node.get_left()       ) - get_height(node.get_right()       ) == 2
												):  # an unbalance detected
																		A__	:							List[str]						    = node.get_left()
																		assert left_child is not None
																		if (
																		    data < left_child.get_data()
																		):  # new node is the left child of the left child
																								A__	:							Optional[int]						    = right_rotation(__lowercase       )
																		else:
																								A__	:							Dict						    = lr_rotation(__lowercase       )
						else:
												node.set_right(insert_node(node.get_right()							,     __lowercase       )       )
												if get_height(node.get_right()       ) - get_height(node.get_left()       ) == 2:
																		A__	:							Optional[Any]						    = node.get_right()
																		assert right_child is not None
																		if data < right_child.get_data():
																								A__	:							List[str]						    = rl_rotation(__lowercase       )
																		else:
																								A__	:							Optional[int]						    = left_rotation(__lowercase       )
						A__	:							List[Any]						    = my_max(get_height(node.get_right()       )							,     get_height(node.get_left()       )       ) + 1
						node.set_height(__lowercase       )
						return node
def 	snake_case__       (					__lowercase       )		->		Any:







						"""simple docstring"""

						while True:
												A__	:							List[Any]						    = root.get_right()
												if right_child is None:
																		break
												A__	:							List[str]						    = right_child
						return root.get_data()
def 	snake_case__       (					__lowercase       )		->		Any:







						"""simple docstring"""

						while True:
												A__	:							Dict						    = root.get_left()
												if left_child is None:
																		break
												A__	:							Tuple						    = left_child
						return root.get_data()
def 	snake_case__       (					__lowercase							,     __lowercase       )		->		MyNode | None:







						"""simple docstring"""

						A__	:							Tuple						    = root.get_left()
						A__	:							Union[str, Any]						    = root.get_right()
						if root.get_data() == data:
												if left_child is not None and right_child is not None:
																		A__	:							Optional[Any]						    = get_left_most(__lowercase       )
																		root.set_data(__lowercase       )
																		root.set_right(del_node(__lowercase							,     __lowercase       )       )
												elif left_child is not None:
																		A__	:							int						    = left_child
												elif right_child is not None:
																		A__	:							int						    = right_child
												else:
																		return None
						elif root.get_data() > data:
												if left_child is None:
																		print("No such data"       )
																		return root
												else:
																		root.set_left(del_node(__lowercase							,     __lowercase       )       )
						else:  # root.get_data() < data
												if right_child is None:
																		return root
												else:
																		root.set_right(del_node(__lowercase							,     __lowercase       )       )

						if get_height(__lowercase       ) - get_height(__lowercase       ) == 2:
												assert right_child is not None
												if get_height(right_child.get_right()       ) > get_height(right_child.get_left()       ):
																		A__	:							Dict						    = left_rotation(__lowercase       )
												else:
																		A__	:							Union[str, Any]						    = rl_rotation(__lowercase       )
						elif get_height(__lowercase       ) - get_height(__lowercase       ) == -2:
												assert left_child is not None
												if get_height(left_child.get_left()       ) > get_height(left_child.get_right()       ):
																		A__	:							Any						    = right_rotation(__lowercase       )
												else:
																		A__	:							List[Any]						    = lr_rotation(__lowercase       )
						A__	:							List[str]						    = my_max(get_height(root.get_right()       )							,     get_height(root.get_left()       )       ) + 1
						root.set_height(__lowercase       )
						return root




class 							lowerCAmelCase__  :







					def __init__(       self      :     str):
											A__	:							MyNode | None						    = None







					def  _lowercase			(       self      :     Union[str, Any]):
											return get_height(self.root)







					def  _lowercase			(       self      :     Union[str, Any]			,		_A      :     Any):
											print("insert:" + str(_A))
											A__	:							Any						    = insert_node(self.root			,		_A)







					def  _lowercase			(       self      :     Any			,		_A      :     Any):
											print("delete:" + str(_A))
											if self.root is None:
																	print("Tree is empty!")
																	return
											A__	:							Tuple						    = del_node(self.root			,		_A)







					def __str__(       self      :     Tuple			,		):  # a level traversale, gives a more intuitive look on the tree
											A__	:							List[Any]						    = ""
											A__	:							List[str]						    = MyQueue()
											q.push(self.root)
											A__	:							List[Any]						    = self.get_height()
											if layer == 0:
																	return output
											A__	:							Optional[Any]						    = 0
											while not q.is_empty():
																	A__	:							int						    = q.pop()
																	A__	:							Optional[Any]						    = " " * int(math.pow(2			,		layer - 1))
																	output += space
																	if node is None:
																							output += "*"
																							q.push(_A)
																							q.push(_A)
																	else:
																							output += str(node.get_data())
																							q.push(node.get_left())
																							q.push(node.get_right())
																	output += space
																	A__	:							Union[str, Any]						    = cnt + 1
																	for i in range(100):
																							if cnt == math.pow(2			,		_A) - 1:
																													A__	:							Any						    = layer - 1
																													if layer == 0:
																																			output += "\n*************************************"
																																			return output
																													output += "\n"
																													break
											output += "\n*************************************"
											return output




def 	snake_case__       (					)		->		None:







						"""simple docstring"""

						import doctest

						doctest.testmod()


if __name__ == "__main__":
		_test()
		snake_case    :						str  =						AVLtree()
		snake_case    :						Optional[Any]  =						list(range(1_0))
		random.shuffle(lst)
		for i in lst:
				t.insert(i)
				print(str(t))
		random.shuffle(lst)
		for i in lst:
				t.del_node(i)
				print(str(t))




from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt
def 	snake_case__       (					__lowercase       )		->		bool:







						"""simple docstring"""

						A__	:							int						    = int(number**0.5       )
						return number == sq * sq
def 	snake_case__       (					__lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase       )		->		tuple[int, int]:







						"""simple docstring"""

						A__	:							int						    = x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
						A__	:							int						    = x_den * y_den * z_den
						A__	:							int						    = gcd(__lowercase							,     __lowercase       )
						top //= hcf
						bottom //= hcf
						return top, bottom
def 	snake_case__       (					__lowercase = 3_5       )		->		int:







						"""simple docstring"""

						A__	:							set						    = set()
						A__	:							int
						A__	:							Fraction						    = Fraction(0       )
						A__	:							tuple[int, int]

						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
																														A__	:							Any						    = x_num * y_den + x_den * y_num
																														A__	:							List[Any]						    = x_den * y_den
																														A__	:							List[Any]						    = gcd(__lowercase							,     __lowercase       )
																														z_num //= hcf
																														z_den //= hcf
																														if 0 < z_num < z_den <= order:
																																				A__	:							List[Any]						    = add_three(
																																				    __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase       )
																																				unique_s.add(__lowercase       )

																														# n=2
																														A__	:							Any						    = (
																														    x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
																														)
																														A__	:							Optional[int]						    = x_den * x_den * y_den * y_den
																														if is_sq(__lowercase       ) and is_sq(__lowercase       ):
																																				A__	:							Union[str, Any]						    = int(sqrt(__lowercase       )       )
																																				A__	:							int						    = int(sqrt(__lowercase       )       )
																																				A__	:							Any						    = gcd(__lowercase							,     __lowercase       )
																																				z_num //= hcf
																																				z_den //= hcf
																																				if 0 < z_num < z_den <= order:
																																										A__	:							List[Any]						    = add_three(
																																										    __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase       )
																																										unique_s.add(__lowercase       )

                    # n=-1
																														A__	:							Tuple						    = x_num * y_num
																														A__	:							int						    = x_den * y_num + x_num * y_den
																														A__	:							List[str]						    = gcd(__lowercase							,     __lowercase       )
																														z_num //= hcf
																														z_den //= hcf
																														if 0 < z_num < z_den <= order:
																																				A__	:							str						    = add_three(
																																				    __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase       )
																																				unique_s.add(__lowercase       )

																														# n=2
																														A__	:							Any						    = x_num * x_num * y_num * y_num
																														A__	:							List[str]						    = (
																														    x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
																														)
																														if is_sq(__lowercase       ) and is_sq(__lowercase       ):
																																				A__	:							Optional[int]						    = int(sqrt(__lowercase       )       )
																																				A__	:							List[Any]						    = int(sqrt(__lowercase       )       )
																																				A__	:							Union[str, Any]						    = gcd(__lowercase							,     __lowercase       )
																																				z_num //= hcf
																																				z_den //= hcf
																																				if 0 < z_num < z_den <= order:
																																										A__	:							Optional[Any]						    = add_three(
																																										    __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase							,     __lowercase       )
																																										unique_s.add(__lowercase       )

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

						return total.denominator + total.numerator


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