

"""simple docstring"""



from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE_					:	Optional[int]							  =						TypeVar('KEY')
SCREAMING_SNAKE_CASE_					:	int							  =						TypeVar('VAL')



@dataclass(frozen=_lowerCamelCase,	slots=_lowerCamelCase				)
class 					a						(       Generic[KEY, VAL]				):



    """simple docstring"""



    UpperCAmelCase						 =					42
    UpperCAmelCase						 =					42



class 					a						(       _Item				):



    """simple docstring"""



    def __init__(     self: Optional[int]       ):






         """simple docstring"""


         super().__init__(UpperCamelCase    ,						UpperCamelCase       )





    def __bool__(     self: Optional[int]       ):






         """simple docstring"""


         return False

SCREAMING_SNAKE_CASE_					:	str							  =						_DeletedItem()



class 					a						(       MutableMapping[KEY, VAL]				):



    """simple docstring"""



    def __init__(     self: int    ,						UpperCamelCase: int = 8    ,						UpperCamelCase: float = 0.75       ):






         """simple docstring"""


         A__										=  initial_block_size
         A__										=  [None] * initial_block_size
         assert 0.0 < capacity_factor < 1.0
         A__										=  capacity_factor
         A__										=  0

    def 				UpperCamelCase	(     self: Dict    ,						UpperCamelCase: KEY       ):






         """simple docstring"""


         return hash(UpperCamelCase       ) % len(self._buckets       )

    def 				UpperCamelCase	(     self: Union[str, Any]    ,						UpperCamelCase: int       ):






         """simple docstring"""


         return (ind + 1) % len(self._buckets       )

    def 				UpperCamelCase	(     self: Optional[int]    ,						UpperCamelCase: int    ,						UpperCamelCase: KEY    ,						UpperCamelCase: VAL       ):






         """simple docstring"""


         A__										=  self._buckets[ind]
         if not stored:
              A__										=  _Item(UpperCamelCase    ,						UpperCamelCase       )
              self._len += 1
              return True
         elif stored.key == key:
              A__										=  _Item(UpperCamelCase    ,						UpperCamelCase       )
              return True
         else:
              return False

    def 				UpperCamelCase	(     self: Tuple       ):






         """simple docstring"""


         A__										=  len(self._buckets       ) * self._capacity_factor
         return len(self       ) >= int(UpperCamelCase       )

    def 				UpperCamelCase	(     self: Optional[Any]       ):






         """simple docstring"""


         if len(self._buckets       ) <= self._initial_block_size:
              return False
         A__										=  len(self._buckets       ) * self._capacity_factor / 2
         return len(self       ) < limit

    def 				UpperCamelCase	(     self: Optional[int]    ,						UpperCamelCase: int       ):






         """simple docstring"""


         A__										=  self._buckets
         A__										=  [None] * new_size
         A__										=  0
         for item in old_buckets:
              if item:
                   self._add_item(item.key    ,						item.val       )

    def 				UpperCamelCase	(     self: List[Any]       ):






         """simple docstring"""


         self._resize(len(self._buckets       ) * 2       )

    def 				UpperCamelCase	(     self: Optional[Any]       ):






         """simple docstring"""


         self._resize(len(self._buckets       ) // 2       )

    def 				UpperCamelCase	(     self: List[Any]    ,						UpperCamelCase: KEY       ):






         """simple docstring"""


         A__										=  self._get_bucket_index(UpperCamelCase       )
         for _ in range(len(self._buckets       )       ):
              yield ind
              A__										=  self._get_next_ind(UpperCamelCase       )

    def 				UpperCamelCase	(     self: Optional[Any]    ,						UpperCamelCase: KEY    ,						UpperCamelCase: VAL       ):






         """simple docstring"""


         for ind in self._iterate_buckets(UpperCamelCase       ):
              if self._try_set(UpperCamelCase    ,						UpperCamelCase    ,						UpperCamelCase       ):
                   break

    def __setitem__(     self: int    ,						UpperCamelCase: KEY    ,						UpperCamelCase: VAL       ):






         """simple docstring"""


         if self._is_full():
              self._size_up()

         self._add_item(UpperCamelCase    ,						UpperCamelCase       )

    def __delitem__(     self: Tuple    ,						UpperCamelCase: KEY       ):






         """simple docstring"""


         for ind in self._iterate_buckets(UpperCamelCase       ):
              A__										=  self._buckets[ind]
              if item is None:
                   raise KeyError(UpperCamelCase       )
              if item is _deleted:
                   continue
              if item.key == key:
                   A__										=  _deleted
                   self._len -= 1
                   break
         if self._is_sparse():
              self._size_down()

    def __getitem__(     self: Optional[Any]    ,						UpperCamelCase: KEY       ):






         """simple docstring"""


         for ind in self._iterate_buckets(UpperCamelCase       ):
              A__										=  self._buckets[ind]
              if item is None:
                   break
              if item is _deleted:
                   continue
              if item.key == key:
                   return item.val
         raise KeyError(UpperCamelCase       )

    def __len__(     self: Any       ):






         """simple docstring"""


         return self._len

    def __iter__(     self: Tuple       ):






         """simple docstring"""


         yield from (item.key for item in self._buckets if item)





    def __repr__(     self: str       ):






         """simple docstring"""


         A__										=  """ ,""".join(
             f"""{item.key}: {item.val}""" for item in self._buckets if item       )
         return f"""HashMap({val_string})"""









"""simple docstring"""



import math
import sys





def  _snake_case     (    UpperCAmelCase_  :					int			):
     if number != int(UpperCAmelCase_			):
          raise ValueError("""the value of input must be a natural number"""			)
     if number < 0:
          raise ValueError("""the value of input must not be a negative number"""			)
     if number == 0:
          return 1
     A__										=  [-1] * (number + 1)
     A__										=  0
     for i in range(1					,   number + 1			):
          A__										=  sys.maxsize
          A__										=  int(math.sqrt(UpperCAmelCase_			)			)
          for j in range(1					,   root + 1			):
               A__										=  1 + answers[i - (j**2)]
               A__										=  min(UpperCAmelCase_					,   UpperCAmelCase_			)
          A__										=  answer
     return answers[number]


if __name__ == "__main__":
 import doctest

 doctest.testmod()






