




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

__UpperCamelCase   :			Union[str, Any]          = TypeVar("KEY")
__UpperCamelCase   :			List[str]          = TypeVar("VAL")

@dataclass(frozen=SCREAMING_SNAKE_CASE__ ,			slots=SCREAMING_SNAKE_CASE__					)
class 						__lowerCAmelCase      (      Generic[KEY, VAL]					):
							UpperCamelCase__   	=    42
							UpperCamelCase__   	=    42







class 						__lowerCAmelCase      (      _Item					):
							def __init__(		self		:int							):







								'''simple docstring'''







								super().__init__(_lowercase						, _lowercase							)





							def __bool__(		self		:Dict							):







								'''simple docstring'''







								return False







__UpperCamelCase   :			Dict          = _DeletedItem()

class 						__lowerCAmelCase      (      MutableMapping[KEY, VAL]					):
							def __init__(		self		:int						, __magic_name__		:int = 8						, __magic_name__		: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  lowerCamelCase__				(		self		:List[Any]						, __magic_name__		:KEY							):







								'''simple docstring'''







								return hash(_lowercase							) % len(self._buckets							)
							def  lowerCamelCase__				(		self		:List[str]						, __magic_name__		:int							):







								'''simple docstring'''







								return (ind + 1) % len(self._buckets							)
							def  lowerCamelCase__				(		self		:Optional[Any]						, __magic_name__		:int						, __magic_name__		:KEY						, __magic_name__		:VAL							):







								'''simple docstring'''







								a									=				self._buckets[ind]
								if not stored:
									a									=				_Item(_lowercase						, _lowercase							)
									self._len += 1
									return True
								elif stored.key == key:
									a									=				_Item(_lowercase						, _lowercase							)
									return True
								else:
									return False
							def  lowerCamelCase__				(		self		:Tuple							):







								'''simple docstring'''







								a									=				len(self._buckets							) * self._capacity_factor
								return len(self							) >= int(_lowercase							)
							def  lowerCamelCase__				(		self		:int							):







								'''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  lowerCamelCase__				(		self		:str						, __magic_name__		: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  lowerCamelCase__				(		self		:Union[str, Any]							):







								'''simple docstring'''







								self._resize(len(self._buckets							) * 2							)
							def  lowerCamelCase__				(		self		:Any							):







								'''simple docstring'''







								self._resize(len(self._buckets							) // 2							)
							def  lowerCamelCase__				(		self		:Dict						, __magic_name__		:KEY							):







								'''simple docstring'''







								a									=				self._get_bucket_index(_lowercase							)
								for _ in range(len(self._buckets							)							):
									yield ind
									a									=				self._get_next_ind(_lowercase							)
							def  lowerCamelCase__				(		self		:str						, __magic_name__		:KEY						, __magic_name__		:VAL							):







								'''simple docstring'''







								for ind in self._iterate_buckets(_lowercase							):
									if self._try_set(_lowercase						, _lowercase						, _lowercase							):
										break
							def __setitem__(		self		:str						, __magic_name__		:KEY						, __magic_name__		:VAL							):







								'''simple docstring'''







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

								self._add_item(_lowercase						, _lowercase							)
							def __delitem__(		self		:Optional[int]						, __magic_name__		:KEY							):







								'''simple docstring'''







								for ind in self._iterate_buckets(_lowercase							):
									a									=				self._buckets[ind]
									if item is None:
										raise KeyError(_lowercase							)
									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		:Union[str, Any]						, __magic_name__		:KEY							):







								'''simple docstring'''







								for ind in self._iterate_buckets(_lowercase							):
									a									=				self._buckets[ind]
									if item is None:
										break
									if item is _deleted:
										continue
									if item.key == key:
										return item.val
								raise KeyError(_lowercase							)
							def __len__(		self		:Union[str, Any]							):







								'''simple docstring'''







								return self._len
							def __iter__(		self		:int							):







								'''simple docstring'''







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





							def __repr__(		self		:Optional[Any]							):







								'''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  __SCREAMING_SNAKE_CASE		(			lowerCamelCase_:							int ):
						"""simple docstring"""






						if number != int(lowerCamelCase_ ):
												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
						snake_case   :			List[str]						    = [-1] * (number + 1)
						snake_case   :			str						    = 0
						for i in range(1     ,		number + 1 ):
												snake_case   :			Tuple						    = sys.maxsize
												snake_case   :			Optional[Any]						    = int(math.sqrt(lowerCamelCase_ ) )
												for j in range(1     ,		root + 1 ):
																		snake_case   :			List[str]						    = 1 + answers[i - (j**2)]
																		snake_case   :			List[str]						    = min(lowerCamelCase_     ,		lowerCamelCase_ )
												snake_case   :			Dict						    = answer
						return answers[number]


if __name__ == "__main__":
			import doctest

			doctest.testmod()



