






from __future__ import annotations

import unittest
from collections.abc import Iterator
class 					a_:



     """simple docstring"""



     def __init__(						self			:					Tuple       ,       lowerCAmelCase__			:					int       ,       lowerCAmelCase__			:					Node | None)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						label
      SCREAMING_SNAKE_CASE							  =						parent
      SCREAMING_SNAKE_CASE							  =						None
      SCREAMING_SNAKE_CASE							  =						None

class 					a_:



     """simple docstring"""



     def __init__(						self			:					Optional[Any])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						None





     def   __UpperCamelCase		(						self			:					Tuple)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						None





     def   __UpperCamelCase		(						self			:					Any)    ->					bool:

      """simple docstring"""
      return self.root is None





     def   __UpperCamelCase		(						self			:					List[str]       ,       lowerCAmelCase__			:					int)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._put(self.root       ,       lowerCAmelCase__)





     def   __UpperCamelCase		(						self			:					int       ,       lowerCAmelCase__			:					Node | None       ,       lowerCAmelCase__			:					int       ,       lowerCAmelCase__			:					Node | None = None)    ->					Node:

      """simple docstring"""
      if node is None:
       SCREAMING_SNAKE_CASE							  =						Node(lowerCAmelCase__       ,       lowerCAmelCase__)
      else:
       if label < node.label:
        SCREAMING_SNAKE_CASE							  =						self._put(node.left       ,       lowerCAmelCase__       ,       lowerCAmelCase__)
       elif label > node.label:
        SCREAMING_SNAKE_CASE							  =						self._put(node.right       ,       lowerCAmelCase__       ,       lowerCAmelCase__)
       else:
        SCREAMING_SNAKE_CASE							  =						f'''Node with label {label} already exists'''
        raise Exception(lowerCAmelCase__)

      return node





     def   __UpperCamelCase		(						self			:					Dict       ,       lowerCAmelCase__			:					int)    ->					Node:

      """simple docstring"""
      return self._search(self.root       ,       lowerCAmelCase__)





     def   __UpperCamelCase		(						self			:					List[Any]       ,       lowerCAmelCase__			:					Node | None       ,       lowerCAmelCase__			:					int)    ->					Node:

      """simple docstring"""
      if node is None:
       SCREAMING_SNAKE_CASE							  =						f'''Node with label {label} does not exist'''
       raise Exception(lowerCAmelCase__)
      else:
       if label < node.label:
        SCREAMING_SNAKE_CASE							  =						self._search(node.left       ,       lowerCAmelCase__)
       elif label > node.label:
        SCREAMING_SNAKE_CASE							  =						self._search(node.right       ,       lowerCAmelCase__)

      return node





     def   __UpperCamelCase		(						self			:					Dict       ,       lowerCAmelCase__			:					int)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self.search(lowerCAmelCase__)
      if node.right and node.left:
       SCREAMING_SNAKE_CASE							  =						self._get_lowest_node(node.right)
       SCREAMING_SNAKE_CASE							  =						node.left
       SCREAMING_SNAKE_CASE							  =						node.right
       SCREAMING_SNAKE_CASE							  =						lowest_node
       if node.right:
        SCREAMING_SNAKE_CASE							  =						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   __UpperCamelCase		(						self			:					Optional[Any]       ,       lowerCAmelCase__			:					Node       ,       lowerCAmelCase__			:					Node | None)    ->					None:

      """simple docstring"""
      if new_children:
       SCREAMING_SNAKE_CASE							  =						node.parent

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





     def   __UpperCamelCase		(						self			:					Dict       ,       lowerCAmelCase__			:					Node)    ->					Node:

      """simple docstring"""
      if node.left:
       SCREAMING_SNAKE_CASE							  =						self._get_lowest_node(node.left)
      else:
       SCREAMING_SNAKE_CASE							  =						node
       self._reassign_nodes(lowerCAmelCase__       ,       node.right)

      return lowest_node





     def   __UpperCamelCase		(						self			:					int       ,       lowerCAmelCase__			:					int)    ->					bool:

      """simple docstring"""
      try:
       self.search(lowerCAmelCase__)
       return True
      except Exception:
       return False





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

      """simple docstring"""
      if self.root is None:
       raise Exception('Binary search tree is empty')

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

      return node.label





     def   __UpperCamelCase		(						self			:					Any)    ->					int:

      """simple docstring"""
      if self.root is None:
       raise Exception('Binary search tree is empty')

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

      return node.label





     def   __UpperCamelCase		(						self			:					str)    ->					Iterator[Node]:

      """simple docstring"""
      return self._inorder_traversal(self.root)





     def   __UpperCamelCase		(						self			:					str       ,       lowerCAmelCase__			:					Node | None)    ->					Iterator[Node]:

      """simple docstring"""
      if node is not None:
       yield from self._inorder_traversal(node.left)
       yield node
       yield from self._inorder_traversal(node.right)





     def   __UpperCamelCase		(						self			:					List[str])    ->					Iterator[Node]:

      """simple docstring"""
      return self._preorder_traversal(self.root)





     def   __UpperCamelCase		(						self			:					Optional[int]       ,       lowerCAmelCase__			:					Node | None)    ->					Iterator[Node]:

      """simple docstring"""
      if node is not None:
       yield node
       yield from self._preorder_traversal(node.left)
       yield from self._preorder_traversal(node.right)

class 					a_(						unittest.TestCase					):



     """simple docstring"""



     @staticmethod
     def   __UpperCamelCase		(						)    ->					BinarySearchTree:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						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)

      return t





     def   __UpperCamelCase		(						self			:					List[str])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						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(1_0)
      assert t.root.right is not None
      assert t.root.right.parent == t.root
      assert t.root.right.label == 1_0

      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   __UpperCamelCase		(						self			:					Tuple)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

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

      SCREAMING_SNAKE_CASE							  =						t.search(1_3)
      assert node.label == 1_3

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





     def   __UpperCamelCase		(						self			:					Union[str, Any])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

      t.remove(1_3)
      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   __UpperCamelCase		(						self			:					Optional[Any])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						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   __UpperCamelCase		(						self			:					Union[str, Any])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()
      t.empty()
      assert t.root is None





     def   __UpperCamelCase		(						self			:					Dict)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()
      assert not t.is_empty()

      t.empty()
      assert t.is_empty()





     def   __UpperCamelCase		(						self			:					Tuple)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

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





     def   __UpperCamelCase		(						self			:					Any)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

      assert t.get_max_label() == 1_4

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





     def   __UpperCamelCase		(						self			:					Optional[int])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

      assert t.get_min_label() == 1

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





     def   __UpperCamelCase		(						self			:					Tuple)    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

      SCREAMING_SNAKE_CASE							  =						[i.label for i in t.inorder_traversal()]
      assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]





     def   __UpperCamelCase		(						self			:					Union[str, Any])    ->					None:

      """simple docstring"""
      SCREAMING_SNAKE_CASE							  =						self._get_binary_search_tree()

      SCREAMING_SNAKE_CASE							  =						[i.label for i in t.preorder_traversal()]
      assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]





def 		A_			(		)							->None:







 """simple docstring"""

 SCREAMING_SNAKE_CASE							  =						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(
     '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '	)

 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
 SCREAMING_SNAKE_CASE							  =						[i.label for i in t.inorder_traversal()]
 print('Inorder traversal:'					,       lowercase_	)

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

 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(
     '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '	)
 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
 SCREAMING_SNAKE_CASE							  =						[i.label for i in t.inorder_traversal()]
 print('Inorder traversal after delete:'					,       lowercase_	)

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

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


if __name__ == "__main__":
      binary_search_tree_example()








import math





def 		A_			(		lowercase_	)							->List[Any]:







 """simple docstring"""

 SCREAMING_SNAKE_CASE							  =						0
 if n % 2 == 0:
  count += 1
  while n % 2 == 0:
   SCREAMING_SNAKE_CASE							  =						int(n / 2	)
    # the n input value must be odd so that
    # we can skip one element (ie i += 2)

 SCREAMING_SNAKE_CASE							  =						3

 while i <= int(math.sqrt(lowercase_	)	):
  if n % i == 0:
   count += 1
   while n % i == 0:
    SCREAMING_SNAKE_CASE							  =						int(n / i	)
  SCREAMING_SNAKE_CASE							  =						i + 2

 # this condition checks the prime
 # number n is greater than 2

 if n > 2:
  count += 1
 return count


if __name__ == "__main__":
      __UpperCAmelCase      				=							5_1_2_4_2_1_8_3
      print(f'The number of distinct prime factors is/are {exact_prime_factor_count(n)}')
      print(f'The value of log(log(n)) is {math.log(math.log(n)):.4f}')




