



from __future__ import annotations

import unittest
from collections.abc import Iterator

class 			__snake_case   :







							'''simple docstring'''






							def __init__(				self	,	a_	,	a_		):
											a__					   =		label
											a__					   =		parent
											a__					   =		None
											a__					   =		None




class 			__snake_case   :







							'''simple docstring'''






							def __init__(				self		):
											a__					   =		None


							def _a   (				self		):
											a__					   =		None


							def _a   (				self		):
											return self.root is None


							def _a   (				self	,	a_		):
											a__					   =		self._put(self.root	,	a_		)


							def _a   (				self	,	a_	,	a_	,	a_ = None		):
											if node is None:
															a__					   =		Node(a_	,	a_		)
											else:
															if label < node.label:
																			a__					   =		self._put(node.left	,	a_	,	a_		)
															elif label > node.label:
																			a__					   =		self._put(node.right	,	a_	,	a_		)
															else:
																			a__					   =		F'''Node with label {label} already exists'''
																			raise Exception(a_		)

											return node


							def _a   (				self	,	a_		):
											return self._search(self.root	,	a_		)


							def _a   (				self	,	a_	,	a_		):
											if node is None:
															a__					   =		F'''Node with label {label} does not exist'''
															raise Exception(a_		)
											else:
															if label < node.label:
																			a__					   =		self._search(node.left	,	a_		)
															elif label > node.label:
																			a__					   =		self._search(node.right	,	a_		)

											return node


							def _a   (				self	,	a_		):
											a__					   =		self.search(a_		)
											if node.right and node.left:
															a__					   =		self._get_lowest_node(node.right		)
															a__					   =		node.left
															a__					   =		node.right
															a__					   =		lowest_node
															if node.right:
																			a__					   =		lowest_node
															self._reassign_nodes(a_	,	a_		)
											elif not node.right and node.left:
															self._reassign_nodes(a_	,	node.left		)
											elif node.right and not node.left:
															self._reassign_nodes(a_	,	node.right		)
											else:
															self._reassign_nodes(a_	,	a_		)


							def _a   (				self	,	a_	,	a_		):
											if new_children:
															a__					   =		node.parent

											if node.parent:
															if node.parent.right == node:
																			a__					   =		new_children
															else:
																			a__					   =		new_children
											else:
															a__					   =		new_children


							def _a   (				self	,	a_		):
											if node.left:
															a__					   =		self._get_lowest_node(node.left		)
											else:
															a__					   =		node
															self._reassign_nodes(a_	,	node.right		)

											return lowest_node


							def _a   (				self	,	a_		):
											try:
															self.search(a_		)
															return True
											except Exception:
															return False


							def _a   (				self		):
											if self.root is None:
															raise Exception("""Binary search tree is empty"""		)

											a__					   =		self.root
											while node.right is not None:
															a__					   =		node.right

											return node.label


							def _a   (				self		):
											if self.root is None:
															raise Exception("""Binary search tree is empty"""		)

											a__					   =		self.root
											while node.left is not None:
															a__					   =		node.left

											return node.label


							def _a   (				self		):
											return self._inorder_traversal(self.root		)


							def _a   (				self	,	a_		):
											if node is not None:
															yield from self._inorder_traversal(node.left		)
															yield node
															yield from self._inorder_traversal(node.right		)


							def _a   (				self		):
											return self._preorder_traversal(self.root		)







							def _a   (				self	,	a_		):
											if node is not None:
															yield node
															yield from self._preorder_traversal(node.left		)
															yield from self._preorder_traversal(node.right		)




class 			__snake_case   ( unittest.TestCase):







							'''simple docstring'''






							@staticmethod
							def _a   (				):
											a__					   =		BinarySearchTree()
											t.put(8		)
											t.put(3		)
											t.put(6		)
											t.put(1		)
											t.put(10		)
											t.put(14		)
											t.put(13		)
											t.put(4		)
											t.put(7		)
											t.put(5		)

											return t


							def _a   (				self		):
											a__					   =		BinarySearchTree()
											assert t.is_empty()

											t.put(8		)
											assert t.root is not None
											assert t.root.parent is None
											assert t.root.label == 8

											t.put(10		)
											assert t.root.right is not None
											assert t.root.right.parent == t.root
											assert t.root.right.label == 10

											t.put(3		)
											assert t.root.left is not None
											assert t.root.left.parent == t.root
											assert t.root.left.label == 3

											t.put(6		)
											assert t.root.left.right is not None
											assert t.root.left.right.parent == t.root.left
											assert t.root.left.right.label == 6

											t.put(1		)
											assert t.root.left.left is not None
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.left.label == 1

											with self.assertRaises(a_		):  # noqa: B017
															t.put(1		)


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											a__					   =		t.search(6		)
											assert node.label == 6

											a__					   =		t.search(13		)
											assert node.label == 13

											with self.assertRaises(a_		):  # noqa: B017
															t.search(2		)


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											t.remove(13		)
											assert t.root is not None
											assert t.root.right is not None
											assert t.root.right.right is not None
											assert t.root.right.right.right is None
											assert t.root.right.right.left is None

											t.remove(7		)
											assert t.root.left is not None
											assert t.root.left.right is not None
											assert t.root.left.right.left is not None
											assert t.root.left.right.right is None
											assert t.root.left.right.left.label == 4

											t.remove(6		)
											assert t.root.left.left is not None
											assert t.root.left.right.right is not None
											assert t.root.left.left.label == 1
											assert t.root.left.right.label == 4
											assert t.root.left.right.right.label == 5
											assert t.root.left.right.left is None
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.right.parent == t.root.left

											t.remove(3		)
											assert t.root is not None
											assert t.root.left.label == 4
											assert t.root.left.right.label == 5
											assert t.root.left.left.label == 1
											assert t.root.left.parent == t.root
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.right.parent == t.root.left

											t.remove(4		)
											assert t.root.left is not None
											assert t.root.left.left is not None
											assert t.root.left.label == 5
											assert t.root.left.right is None
											assert t.root.left.left.label == 1
											assert t.root.left.parent == t.root
											assert t.root.left.left.parent == t.root.left


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											t.remove(3		)
											assert t.root is not None
											assert t.root.left is not None
											assert t.root.left.left is not None
											assert t.root.left.right is not None
											assert t.root.left.right.left is not None
											assert t.root.left.right.right is not None
											assert t.root.left.label == 4
											assert t.root.left.right.label == 6
											assert t.root.left.left.label == 1
											assert t.root.left.right.right.label == 7
											assert t.root.left.right.left.label == 5
											assert t.root.left.parent == t.root
											assert t.root.left.right.parent == t.root.left
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.right.left.parent == t.root.left.right


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()
											t.empty()
											assert t.root is None


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()
											assert not t.is_empty()

											t.empty()
											assert t.is_empty()


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											assert t.exists(6		)
											assert not t.exists(-1		)


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											assert t.get_max_label() == 14

											t.empty()
											with self.assertRaises(a_		):  # noqa: B017
															t.get_max_label()


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											assert t.get_min_label() == 1

											t.empty()
											with self.assertRaises(a_		):  # noqa: B017
															t.get_min_label()


							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											a__					   =		[i.label for i in t.inorder_traversal()]
											assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]







							def _a   (				self		):
											a__					   =		self._get_binary_search_tree()

											a__					   =		[i.label for i in t.preorder_traversal()]
											assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]




def       A_   (						):

				"""simple docstring"""
				a__					   =		BinarySearchTree()
				t.put(8		)
				t.put(3		)
				t.put(6		)
				t.put(1		)
				t.put(10		)
				t.put(14		)
				t.put(13		)
				t.put(4		)
				t.put(7		)
				t.put(5		)

				print(
				    """
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        """		)

				print("""Label 6 exists:"""			,		t.exists(6		)		)
				print("""Label 13 exists:"""			,		t.exists(13		)		)
				print("""Label -1 exists:"""			,		t.exists(-1		)		)
				print("""Label 12 exists:"""			,		t.exists(12		)		)

				# Prints all the elements of the list in inorder traversal
				a__					   =		[i.label for i in t.inorder_traversal()]
				print("""Inorder traversal:"""			,		__a		)

				# Prints all the elements of the list in preorder traversal
				a__					   =		[i.label for i in t.preorder_traversal()]
				print("""Preorder traversal:"""			,		__a		)

				print("""Max. label:"""			,		t.get_max_label()		)
				print("""Min. label:"""			,		t.get_min_label()		)

				# Delete elements
				print("""\nDeleting elements 13, 10, 8, 3, 6, 14"""		)
				print(
				    """
          4
         / \\
        1   7
             \\
              5
        """		)
				t.remove(13		)
				t.remove(10		)
				t.remove(8		)
				t.remove(3		)
				t.remove(6		)
				t.remove(14		)

				# Prints all the elements of the list in inorder traversal after delete
				a__					   =		[i.label for i in t.inorder_traversal()]
				print("""Inorder traversal after delete:"""			,		__a		)

				# Prints all the elements of the list in preorder traversal after delete
				a__					   =		[i.label for i in t.preorder_traversal()]
				print("""Preorder traversal after delete:"""			,		__a		)

				print("""Max. label:"""			,		t.get_max_label()		)
				print("""Min. label:"""			,		t.get_min_label()		)


if __name__ == "__main__":
	binary_search_tree_example()






from math import gcd

def       A_   (						__a  :					int = 12_000		):

				"""simple docstring"""
				a__					   =		0
				for d in range(max_d + 1		):
								for n in range(d // 3 + 1			,		(d + 1) // 2		):
												if gcd(__a			,		__a		) == 1:
																fractions_number += 1
				return fractions_number


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

