

"""simple docstring"""


from __future__ import annotations

from functools import lru_cache
from math import ceil

__A						       =      100

__A						       =      set(range(3, NUM_PRIMES, 2))
primes.add(2)
__A						       =      42

for prime in range(3, ceil(NUM_PRIMES**0.5), 2):
			if prime not in primes:
						continue
			primes.difference_update(set(range(prime * prime, NUM_PRIMES, prime)))






@lru_cache(maxsize=1_0_0			)
def    a__   (   __SCREAMING_SNAKE_CASE			)     ->     set[int]:
		if number_to_partition < 0:
				return set()
		elif number_to_partition == 0:
				return {1}

		__lowerCAmelCase:	set[int]   				=      set()
		__lowerCAmelCase:	int
		__lowerCAmelCase:	int

		for prime in primes:
				if prime > number_to_partition:
						continue
				for sub in partition(number_to_partition - prime			):
						ret.add(sub * prime			)

		return ret






def    a__   (   __SCREAMING_SNAKE_CASE = 5_0_0_0			)     ->     int | None:
		for number_to_partition in range(1 ,			__SCREAMING_SNAKE_CASE			):
				if len(partition(__SCREAMING_SNAKE_CASE			)			) > number_unique_partitions:
						return number_to_partition
		return None


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





"""simple docstring"""


import math
import sys






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


if __name__ == "__main__":
			import doctest

			doctest.testmod()


