






'''simple docstring'''







from __future__ import annotations

import unittest
from collections.abc import Iterator




class 					__UpperCAmelCase :

      '''simple docstring'''





      def __init__(					self  ,		_UpperCAmelCase  ,		_UpperCAmelCase						):
             UpperCAmelCase__	:   Tuple												=	label
             UpperCAmelCase__	:   Dict												=	parent
             UpperCAmelCase__	:   Node | None												=	None
             UpperCAmelCase__	:   Node | None												=	None




class 					__UpperCAmelCase :

      '''simple docstring'''





      def __init__(					self						):
             UpperCAmelCase__	:   Node | None												=	None




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   List[str]												=	None




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




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase						):
             UpperCAmelCase__	:   List[Any]												=	self._put(self.root  ,		lowerCamelCase_						)




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase  ,		_UpperCAmelCase  ,		_UpperCAmelCase = None						):
             if node is None:
                    UpperCAmelCase__	:   Tuple												=	Node(lowerCamelCase_  ,		lowerCamelCase_						)
             else:
                    if label < node.label:
                           UpperCAmelCase__	:   Tuple												=	self._put(node.left  ,		lowerCamelCase_  ,		lowerCamelCase_						)
                    elif label > node.label:
                           UpperCAmelCase__	:   int												=	self._put(node.right  ,		lowerCamelCase_  ,		lowerCamelCase_						)
                    else:
                           UpperCAmelCase__	:   Optional[int]												=	F"""Node with label {label} already exists"""
                           raise Exception(lowerCamelCase_						)

             return node




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase						):
             return self._search(self.root  ,		lowerCamelCase_						)




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase  ,		_UpperCAmelCase						):
             if node is None:
                    UpperCAmelCase__	:   Dict												=	F"""Node with label {label} does not exist"""
                    raise Exception(lowerCamelCase_						)
             else:
                    if label < node.label:
                           UpperCAmelCase__	:   Optional[Any]												=	self._search(node.left  ,		lowerCamelCase_						)
                    elif label > node.label:
                           UpperCAmelCase__	:   str												=	self._search(node.right  ,		lowerCamelCase_						)

             return node




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase						):
             UpperCAmelCase__	:   Union[str, Any]												=	self.search(lowerCamelCase_						)
             if node.right and node.left:
                    UpperCAmelCase__	:   List[Any]												=	self._get_lowest_node(node.right						)
                    UpperCAmelCase__	:   str												=	node.left
                    UpperCAmelCase__	:   Any												=	node.right
                    UpperCAmelCase__	:   List[str]												=	lowest_node
                    if node.right:
                           UpperCAmelCase__	:   Tuple												=	lowest_node
                    self._reassign_nodes(lowerCamelCase_  ,		lowerCamelCase_						)
             elif not node.right and node.left:
                    self._reassign_nodes(lowerCamelCase_  ,		node.left						)
             elif node.right and not node.left:
                    self._reassign_nodes(lowerCamelCase_  ,		node.right						)
             else:
                    self._reassign_nodes(lowerCamelCase_  ,		lowerCamelCase_						)




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase  ,		_UpperCAmelCase						):
             if new_children:
                    UpperCAmelCase__	:   Dict												=	node.parent

             if node.parent:
                    if node.parent.right == node:
                           UpperCAmelCase__	:   Tuple												=	new_children
                    else:
                           UpperCAmelCase__	:   Optional[int]												=	new_children
             else:
                    UpperCAmelCase__	:   List[str]												=	new_children




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase						):
             if node.left:
                    UpperCAmelCase__	:   Any												=	self._get_lowest_node(node.left						)
             else:
                    UpperCAmelCase__	:   List[Any]												=	node
                    self._reassign_nodes(lowerCamelCase_  ,		node.right						)

             return lowest_node




      def 							lowerCamelCase     (					self  ,		_UpperCAmelCase						):
             try:
                    self.search(lowerCamelCase_						)
                    return True
             except Exception:
                    return False




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

             UpperCAmelCase__	:   List[Any]												=	self.root
             while node.right is not None:
                    UpperCAmelCase__	:   Any												=	node.right

             return node.label




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

             UpperCAmelCase__	:   Dict												=	self.root
             while node.left is not None:
                    UpperCAmelCase__	:   Optional[int]												=	node.left

             return node.label




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




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




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




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




class 					__UpperCAmelCase (		unittest.TestCase	):

      '''simple docstring'''





      @staticmethod
      def 							lowerCamelCase     (					):
             UpperCAmelCase__	:   Tuple												=	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 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   List[str]												=	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(lowerCamelCase_						):  # noqa: B017
                    t.put(1						)




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   List[Any]												=	self._get_binary_search_tree()

             UpperCAmelCase__	:   Dict												=	t.search(6						)
             assert node.label == 6

             UpperCAmelCase__	:   Any												=	t.search(13						)
             assert node.label == 13

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




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Optional[int]												=	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 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Tuple												=	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 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Optional[int]												=	self._get_binary_search_tree()
             t.empty()
             assert t.root is None




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Optional[int]												=	self._get_binary_search_tree()
             assert not t.is_empty()

             t.empty()
             assert t.is_empty()




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Any												=	self._get_binary_search_tree()

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




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Optional[Any]												=	self._get_binary_search_tree()

             assert t.get_max_label() == 14

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




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Optional[int]												=	self._get_binary_search_tree()

             assert t.get_min_label() == 1

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




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   Union[str, Any]												=	self._get_binary_search_tree()

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




      def 							lowerCamelCase     (					self						):
             UpperCAmelCase__	:   List[Any]												=	self._get_binary_search_tree()

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






def  lowerCAmelCase__		(					)   -> Union[str, Any]:
       UpperCAmelCase__	:   Tuple												=	BinarySearchTree()
       t.put(8			)
       t.put(3			)
       t.put(6			)
       t.put(1			)
       t.put(1_0			)
       t.put(1_4			)
       t.put(1_3			)
       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(1_3			)			)
       print('''Label -1 exists:'''			,						t.exists(-1			)			)
       print('''Label 12 exists:'''			,						t.exists(1_2			)			)

       # Prints all the elements of the list in inorder traversal
       UpperCAmelCase__	:   Optional[Any]												=	[i.label for i in t.inorder_traversal()]
       print('''Inorder traversal:'''			,						_a			)

       # Prints all the elements of the list in preorder traversal
       UpperCAmelCase__	:   List[Any]												=	[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(1_3			)
       t.remove(1_0			)
       t.remove(8			)
       t.remove(3			)
       t.remove(6			)
       t.remove(1_4			)

       # Prints all the elements of the list in inorder traversal after delete
       UpperCAmelCase__	:   Optional[Any]												=	[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
       UpperCAmelCase__	:   Optional[int]												=	[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()




import math







def       lowerCamelCase_  (    _a       :						int    ):



    '''simple docstring'''




    if 1 < number < 4:
        # 2 and 3 are primes
        return True
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
        # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
        return False

    # All primes number are in format of 6k +/- 1
    for i in range(5   ,		int(math.sqrt(_a    ) + 1    )   ,		6    ):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True







def       lowerCamelCase_  (    _a       :						int = 6008_5147_5143    ):



    '''simple docstring'''




    try:
        UpperCAmelCase_     :       str  		=					int(_a    )
    except (TypeError, ValueError):
        raise TypeError("""Parameter n must be int or castable to int."""    )
    if n <= 0:
        raise ValueError("""Parameter n must be greater than or equal to one."""    )
    UpperCAmelCase_     :       Optional[int]  		=					0
    if is_prime(_a    ):
        return n
    while n % 2 == 0:
        n //= 2
    if is_prime(_a    ):
        return n
    for i in range(3   ,		int(math.sqrt(_a    )    ) + 1   ,		2    ):
        if n % i == 0:
            if is_prime(n // i    ):
                UpperCAmelCase_     :       Optional[int]  		=					n // i
                break
            elif is_prime(_a    ):
                UpperCAmelCase_     :       str  		=					i
    return max_number


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