



from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

UpperCAmelCase_          =				TypeVar("T")
UpperCAmelCase_          =				TypeVar("U")





class 		UpperCAmelCase    (    Generic[T, U]					):





   def __init__(						self							,  _lowerCAmelCase							,  _lowerCAmelCase      ):
         _lowerCAmelCase			      =	key
         _lowerCAmelCase			      =	val
         _lowerCAmelCase			      =	0
         _lowerCAmelCase			      =	None
         _lowerCAmelCase			      =	None





   def __repr__(						self      ):
         return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
             self.key							,  self.val							,  self.freq							,  self.next is not None							,  self.prev is not None      )






class 		UpperCAmelCase    (    Generic[T, U]					):





   def __init__(						self      ):
         _lowerCAmelCase			      =	DoubleLinkedListNode(_lowerCAmelCase							,  _lowerCAmelCase      )
         _lowerCAmelCase			      =	DoubleLinkedListNode(_lowerCAmelCase							,  _lowerCAmelCase      )
         _lowerCAmelCase      , _lowerCAmelCase			      =	self.rear, self.head





   def __repr__(						self      ):
         _lowerCAmelCase			      =	['''DoubleLinkedList''']
         _lowerCAmelCase			      =	self.head
         while node.next is not None:
               rep.append(str(_lowerCAmelCase      )      )
               _lowerCAmelCase			      =	node.next
         rep.append(str(self.rear      )      )
         return ",\n    ".join(_lowerCAmelCase      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         _lowerCAmelCase			      =	self.rear.prev

         # All nodes other than self.head are guaranteed to have non-None previous
         assert previous is not None

         _lowerCAmelCase			      =	node
         _lowerCAmelCase			      =	previous
         _lowerCAmelCase			      =	node
         _lowerCAmelCase			      =	self.rear
         node.freq += 1
         self._position_node(_lowerCAmelCase      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):

         while node.prev is not None and node.prev.freq > node.freq:
               # swap node with previous node
               _lowerCAmelCase			      =	node.prev

               _lowerCAmelCase			      =	previous_node.prev
               _lowerCAmelCase			      =	node.prev
               _lowerCAmelCase			      =	previous_node
               _lowerCAmelCase			      =	node





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):

         if node.prev is None or node.next is None:
               return None

         _lowerCAmelCase			      =	node.next
         _lowerCAmelCase			      =	node.prev
         _lowerCAmelCase			      =	None
         _lowerCAmelCase			      =	None
         return node






class 		UpperCAmelCase    (    Generic[T, U]					):
   SCREAMING_SNAKE_CASE__					      =  {}





   def __init__(						self							,  _lowerCAmelCase      ):
         _lowerCAmelCase			      =	DoubleLinkedList()
         _lowerCAmelCase			      =	capacity
         _lowerCAmelCase			      =	0
         _lowerCAmelCase			      =	0
         _lowerCAmelCase			      =	0
         _lowerCAmelCase			      =	{}





   def __repr__(						self      ):
         return (
             F'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
             F'''capacity={self.capacity}, current_size={self.num_keys})'''
         )





   def __contains__(						self							,  _lowerCAmelCase      ):
         return key in self.cache





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):

         if key in self.cache:
               self.hits += 1
               _lowerCAmelCase			      =	self.cache[key]
               _lowerCAmelCase			      =	self.list.remove(self.cache[key]      )
               assert node == value_node

               # node is guaranteed not None because it is in self.cache
               assert node is not None
               self.list.add(_lowerCAmelCase      )
               return node.val
         self.miss += 1
         return None





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase							,  _lowerCAmelCase      ):

         if key not in self.cache:
               if self.num_keys >= self.capacity:
                     # delete first node when over capacity
                     _lowerCAmelCase			      =	self.list.head.next

                     # guaranteed to have a non-None first node when num_keys > 0
                     # explain to type checker via assertions
                     assert first_node is not None
                     assert first_node.key is not None
                     assert self.list.remove(_lowerCAmelCase      ) is not None
                     # first_node guaranteed to be in list

                     del self.cache[first_node.key]
                     self.num_keys -= 1
               _lowerCAmelCase			      =	DoubleLinkedListNode(_lowerCAmelCase							,  _lowerCAmelCase      )
               self.list.add(self.cache[key]      )
               self.num_keys += 1

         else:
               _lowerCAmelCase			      =	self.list.remove(self.cache[key]      )
               assert node is not None  # node guaranteed to be in list
               _lowerCAmelCase			      =	value
               self.list.add(_lowerCAmelCase      )





   @classmethod
   def 						__lowerCAmelCase				(						cls							,  _lowerCAmelCase = 128      ):

         def cache_decorator_inner(_lowerCAmelCase      ) -> Callable[..., U]:
               def cache_decorator_wrapper(*_lowerCAmelCase      ) -> U:
                     if func not in cls.decorator_function_to_instance_map:
                           _lowerCAmelCase			      =	LFUCache(_lowerCAmelCase      )

                     _lowerCAmelCase			      =	cls.decorator_function_to_instance_map[func].get(args[0]      )
                     if result is None:
                           _lowerCAmelCase			      =	func(*_lowerCAmelCase      )
                           cls.decorator_function_to_instance_map[func].put(args[0]							,  _lowerCAmelCase      )
                     return result

               def cache_info() -> LFUCache[T, U]:
                     return cls.decorator_function_to_instance_map[func]

               setattr(_lowerCAmelCase							,  '''cache_info'''							,  _lowerCAmelCase      )  # noqa: B010

               return cache_decorator_wrapper

         return cache_decorator_inner


if __name__ == "__main__":
    import doctest

    doctest.testmod()




import math
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int					)->bool:

      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(_SCREAMING_SNAKE_CASE					) + 1					)  ,					6					):
            if number % i == 0 or number % (i + 2) == 0:
                  return False
      return True
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int = 6_0_0_8_5_1_4_7_5_1_4_3					)->int:

      try:
            _lowerCAmelCase			      =	int(_SCREAMING_SNAKE_CASE					)
      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.'''					)
      _lowerCAmelCase			      =	0
      if is_prime(_SCREAMING_SNAKE_CASE					):
            return n
      while n % 2 == 0:
            n //= 2
      if is_prime(_SCREAMING_SNAKE_CASE					):
            return n
      for i in range(3  ,					int(math.sqrt(_SCREAMING_SNAKE_CASE					)					) + 1  ,					2					):
            if n % i == 0:
                  if is_prime(n // i					):
                        _lowerCAmelCase			      =	n // i
                        break
                  elif is_prime(_SCREAMING_SNAKE_CASE					):
                        _lowerCAmelCase			      =	i
      return max_number


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