


'''simple docstring'''



from __future__ import annotations

from random import random
from typing import Generic, TypeVar

A__						:   int				=    TypeVar("""KT""")
A__						:   Optional[int]				=    TypeVar("""VT""")





class   UpperCAmelCase_    (Generic[KT, VT]    ):





    """simple docstring"""






    def __init__(				self     ,	SCREAMING_SNAKE_CASE_ = "root"     ,	SCREAMING_SNAKE_CASE_ = None      )							->	Union[str, Any]:
         __lowerCamelCase  :      int														=						key
         __lowerCamelCase  :      Union[str, Any]														=						value
         __lowerCamelCase  :      list[Node[KT, VT]]														=						[]







    def __repr__(				self      )							->	str:
         return f'Node({self.key}: {self.value})'







    @property
    def  lowercase_							(				self      )							->	int:
         return len(self.forward      )







class   UpperCAmelCase_    (Generic[KT, VT]    ):





    """simple docstring"""






    def __init__(				self     ,	SCREAMING_SNAKE_CASE_ = 0.5     ,	SCREAMING_SNAKE_CASE_ = 16      )							->	Optional[int]:
         __lowerCamelCase  :      Node[KT, VT]														=						Node[KT, VT]()
         __lowerCamelCase  :      Tuple														=						0
         __lowerCamelCase  :      List[str]														=						p
         __lowerCamelCase  :      Optional[int]														=						max_level







    def __str__(				self      )							->	str:
         __lowerCamelCase  :      int														=						list(self      )

         if len(SCREAMING_SNAKE_CASE_      ) == 0:
              return f'SkipList(level={self.level})'

         __lowerCamelCase  :      List[str]														=						max((len(str(SCREAMING_SNAKE_CASE_      )      ) for item in items)     ,	default=4      )
         __lowerCamelCase  :      Tuple														=						max(SCREAMING_SNAKE_CASE_     ,	4      ) + 4

         __lowerCamelCase  :      Optional[Any]														=						self.head
         __lowerCamelCase  :      Optional[Any]														=						[]

         __lowerCamelCase  :      int														=						node.forward.copy()
         lines.append(f'[{node.key}]'.ljust(SCREAMING_SNAKE_CASE_     ,	'-'      ) + '* ' * len(SCREAMING_SNAKE_CASE_      )      )
         lines.append(' ' * label_size + '| ' * len(SCREAMING_SNAKE_CASE_      )      )

         while len(node.forward      ) != 0:
              __lowerCamelCase  :      Dict														=						node.forward[0]

              lines.append(
                  f'[{node.key}]'.ljust(SCREAMING_SNAKE_CASE_     ,	'-'      )
                  + ' '.join(str(n.key      ) if n.key == node.key else '|' for n in forwards      )      )
              lines.append(' ' * label_size + '| ' * len(SCREAMING_SNAKE_CASE_      )      )
              __lowerCamelCase  :      Tuple														=						node.forward

         lines.append('None'.ljust(SCREAMING_SNAKE_CASE_      ) + '* ' * len(SCREAMING_SNAKE_CASE_      )      )
         return f'SkipList(level={self.level})\n' + "\n".join(SCREAMING_SNAKE_CASE_      )







    def __iter__(				self      )							->	int:
         __lowerCamelCase  :      Tuple														=						self.head

         while len(node.forward      ) != 0:
              yield node.forward[0].key
              __lowerCamelCase  :      str														=						node.forward[0]







    def  lowercase_							(				self      )							->	int:
         __lowerCamelCase  :      Optional[Any]														=						1
         while random() < self.p and level < self.max_level:
              level += 1

         return level







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
         __lowerCamelCase  :      List[Any]														=						[]

         __lowerCamelCase  :      Any														=						self.head

         for i in reversed(range(self.level      )      ):
              # i < node.level - When node level is lesser than `i` decrement `i`.
              # node.forward[i].key < key - Jumping to node with key value higher
              #                             or equal to searched key would result
              #                             in skipping searched key.
              while i < node.level and node.forward[i].key < key:
                   __lowerCamelCase  :      Any														=						node.forward[i]
              # Each leftmost node (relative to searched node) will potentially have to
              # be updated.
              update_vector.append(SCREAMING_SNAKE_CASE_      )

         update_vector.reverse()  # Note that we were inserting values in reverse order.

         # len(node.forward) != 0 - If current node doesn't contain any further
         #                          references then searched key is not present.
         # node.forward[0].key == key - Next node key should be equal to search key
         #                              if key is present.
         if len(node.forward      ) != 0 and node.forward[0].key == key:
              return node.forward[0], update_vector
         else:
              return None, update_vector







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	Dict:
         __lowerCamelCase							,			__lowerCamelCase  :      Any														=						self._locate_node(SCREAMING_SNAKE_CASE_      )

         if node is not None:
              for i, update_node in enumerate(SCREAMING_SNAKE_CASE_      ):
                   # Remove or replace all references to removed node.
                   if update_node.level > i and update_node.forward[i].key == key:
                        if node.level > i:
                             __lowerCamelCase  :      List[str]														=						node.forward[i]
                        else:
                             __lowerCamelCase  :      Dict														=						update_node.forward[:i]







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Optional[int]:
         __lowerCamelCase							,			__lowerCamelCase  :      Optional[Any]														=						self._locate_node(SCREAMING_SNAKE_CASE_      )
         if node is not None:
              __lowerCamelCase  :      Tuple														=						value
         else:
              __lowerCamelCase  :      str														=						self.random_level()

              if level > self.level:
                   # After level increase we have to add additional nodes to head.
                   for _ in range(self.level - 1     ,	SCREAMING_SNAKE_CASE_      ):
                        update_vector.append(self.head      )
                   __lowerCamelCase  :      List[str]														=						level

              __lowerCamelCase  :      Optional[int]														=						Node(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )

              for i, update_node in enumerate(update_vector[:level]      ):
                   # Change references to pass through new node.
                   if update_node.level > i:
                        new_node.forward.append(update_node.forward[i]      )

                   if update_node.level < i + 1:
                        update_node.forward.append(SCREAMING_SNAKE_CASE_      )
                   else:
                        __lowerCamelCase  :      List[str]														=						new_node







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	VT | None:
         __lowerCamelCase							,			__lowerCamelCase  :      Optional[Any]														=						self._locate_node(SCREAMING_SNAKE_CASE_      )

         if node is not None:
              return node.value

         return None







def      UpperCAmelCase__   (      )	->						Optional[Any]:
     __lowerCamelCase  :      Optional[int]														=						SkipList()
     skip_list.insert('Key1' ,       3				)
     skip_list.insert('Key2' ,       12				)
     skip_list.insert('Key3' ,       41				)
     skip_list.insert('Key4' ,       -19				)

     __lowerCamelCase  :      str														=						skip_list.head
     __lowerCamelCase  :      str														=						{}
     while node.level != 0:
          __lowerCamelCase  :      str														=						node.forward[0]
          __lowerCamelCase  :      Tuple														=						node.value

     assert len(UpperCAmelCase_				) == 4
     assert all_values["Key1"] == 3
     assert all_values["Key2"] == 12
     assert all_values["Key3"] == 41
     assert all_values["Key4"] == -19



def      UpperCAmelCase__   (      )	->						Optional[Any]:
     __lowerCamelCase  :      List[Any]														=						SkipList()
     skip_list.insert('Key1' ,       10				)
     skip_list.insert('Key1' ,       12				)

     skip_list.insert('Key5' ,       7				)
     skip_list.insert('Key7' ,       10				)
     skip_list.insert('Key10' ,       5				)

     skip_list.insert('Key7' ,       7				)
     skip_list.insert('Key5' ,       5				)
     skip_list.insert('Key10' ,       10				)

     __lowerCamelCase  :      Dict														=						skip_list.head
     __lowerCamelCase  :      Optional[Any]														=						{}
     while node.level != 0:
          __lowerCamelCase  :      Tuple														=						node.forward[0]
          __lowerCamelCase  :      List[str]														=						node.value

     if len(UpperCAmelCase_				) != 4:
          print()
     assert len(UpperCAmelCase_				) == 4
     assert all_values["Key1"] == 12
     assert all_values["Key7"] == 7
     assert all_values["Key5"] == 5
     assert all_values["Key10"] == 10



def      UpperCAmelCase__   (      )	->						Optional[Any]:
     __lowerCamelCase  :      str														=						SkipList()
     assert skip_list.find('Some key'				) is None



def      UpperCAmelCase__   (      )	->						List[Any]:
     __lowerCamelCase  :      List[Any]														=						SkipList()

     skip_list.insert('Key2' ,       20				)
     assert skip_list.find('Key2'				) == 20

     skip_list.insert('Some Key' ,       10				)
     skip_list.insert('Key2' ,       8				)
     skip_list.insert('V' ,       13				)

     assert skip_list.find('Y'				) is None
     assert skip_list.find('Key2'				) == 8
     assert skip_list.find('Some Key'				) == 10
     assert skip_list.find('V'				) == 13



def      UpperCAmelCase__   (      )	->						Optional[int]:
     __lowerCamelCase  :      Dict														=						SkipList()
     skip_list.delete('Some key'				)

     assert len(skip_list.head.forward				) == 0



def      UpperCAmelCase__   (      )	->						int:
     __lowerCamelCase  :      Optional[int]														=						SkipList()

     skip_list.insert('Key1' ,       12				)
     skip_list.insert('V' ,       13				)
     skip_list.insert('X' ,       14				)
     skip_list.insert('Key2' ,       15				)

     skip_list.delete('V'				)
     skip_list.delete('Key2'				)

     assert skip_list.find('V'				) is None
     assert skip_list.find('Key2'				) is None



def      UpperCAmelCase__   (      )	->						Tuple:
     __lowerCamelCase  :      Optional[Any]														=						SkipList()

     skip_list.insert('Key1' ,       12				)
     skip_list.insert('V' ,       13				)
     skip_list.insert('X' ,       14				)
     skip_list.insert('Key2' ,       15				)

     skip_list.delete('V'				)
     assert skip_list.find('V'				) is None
     assert skip_list.find('X'				) == 14
     assert skip_list.find('Key1'				) == 12
     assert skip_list.find('Key2'				) == 15

     skip_list.delete('X'				)
     assert skip_list.find('V'				) is None
     assert skip_list.find('X'				) is None
     assert skip_list.find('Key1'				) == 12
     assert skip_list.find('Key2'				) == 15

     skip_list.delete('Key1'				)
     assert skip_list.find('V'				) is None
     assert skip_list.find('X'				) is None
     assert skip_list.find('Key1'				) is None
     assert skip_list.find('Key2'				) == 15

     skip_list.delete('Key2'				)
     assert skip_list.find('V'				) is None
     assert skip_list.find('X'				) is None
     assert skip_list.find('Key1'				) is None
     assert skip_list.find('Key2'				) is None



def      UpperCAmelCase__   (      )	->						int:
     __lowerCamelCase  :      Optional[int]														=						SkipList()

     skip_list.insert('Key1' ,       12				)
     skip_list.insert('V' ,       13				)
     skip_list.insert('X' ,       1_42				)
     skip_list.insert('Key2' ,       15				)

     skip_list.delete('X'				)

     def traverse_keys(UpperCAmelCase_       :							Union[str, Any]				):
          yield node.key
          for forward_node in node.forward:
               yield from traverse_keys(UpperCAmelCase_				)

     assert len(set(traverse_keys(skip_list.head				)				)				) == 4



def      UpperCAmelCase__   (      )	->						int:
     def is_sorted(UpperCAmelCase_       :							Optional[int]				):
          return all(next_item >= item for item, next_item in zip(UpperCAmelCase_ ,       lst[1:]				)				)

     __lowerCamelCase  :      Optional[Any]														=						SkipList()
     for i in range(10				):
          skip_list.insert(UpperCAmelCase_ ,       UpperCAmelCase_				)
     assert is_sorted(list(UpperCAmelCase_				)				)
     skip_list.delete(5				)
     skip_list.delete(8				)
     skip_list.delete(2				)
     assert is_sorted(list(UpperCAmelCase_				)				)
     skip_list.insert(-12 ,       -12				)
     skip_list.insert(77 ,       77				)
     assert is_sorted(list(UpperCAmelCase_				)				)



def      UpperCAmelCase__   (      )	->						Optional[Any]:
     for _ in range(1_00				):
          # Repeat test 100 times due to the probabilistic nature of skip list
          # random values == random bugs
          test_insert()
          test_insert_overrides_existing_value()

          test_searching_empty_list_returns_none()
          test_search()

          test_deleting_item_from_empty_list_do_nothing()
          test_deleted_items_are_not_founded_by_find_method()
          test_delete_removes_only_given_key()
          test_delete_doesnt_leave_dead_nodes()

          test_iter_always_yields_sorted_values()



def      UpperCAmelCase__   (      )	->						List[Any]:
     __lowerCamelCase  :      Tuple														=						SkipList()
     skip_list.insert(2 ,       '2'				)
     skip_list.insert(4 ,       '4'				)
     skip_list.insert(6 ,       '4'				)
     skip_list.insert(4 ,       '5'				)
     skip_list.insert(8 ,       '4'				)
     skip_list.insert(9 ,       '4'				)

     skip_list.delete(4				)

     print(UpperCAmelCase_				)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      main()










'''simple docstring'''



from collections import defaultdict
from math import gcd



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int = 1_50_00_00				)	->						int:
     __lowerCamelCase  :      defaultdict														=						defaultdict(UpperCAmelCase_				)
     __lowerCamelCase  :      Any														=						2
     while 2 * euclid_m * (euclid_m + 1) <= limit:
          for euclid_n in range((euclid_m % 2) + 1 ,       UpperCAmelCase_ ,       2				):
               if gcd(UpperCAmelCase_ ,       UpperCAmelCase_				) > 1:
                    continue
               __lowerCamelCase  :      Any														=						2 * euclid_m * (euclid_m + euclid_n)
               for perimeter in range(UpperCAmelCase_ ,       limit + 1 ,       UpperCAmelCase_				):
                    frequencies[perimeter] += 1
          euclid_m += 1
     return sum(1 for frequency in frequencies.values() if frequency == 1				)


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






