

# Lint as: python3
import itertools
import os
import re


snake_case_        =			re.compile(r'''([A-Z]+)([A-Z][a-z])''')
snake_case_        =			re.compile(r'''([a-z\d])([A-Z])''')

snake_case_        =			re.compile(r'''(?<!_)_(?!_)''')
snake_case_        =			re.compile(r'''(_{2,})''')

snake_case_        =			r'''^\w+(\.\w+)*$'''

snake_case_        =			r'''<>:/\|?*'''

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   str      ):



     '''simple docstring'''





     lowercase__   :       Optional[Any]				=	_uppercase_uppercase_re.sub(R'\1_\2'     ,					SCREAMING_SNAKE_CASE_      )
     lowercase__   :       Any				=	_lowercase_uppercase_re.sub(R'\1_\2'     ,					SCREAMING_SNAKE_CASE_      )
     return name.lower()

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   Tuple      ):



     '''simple docstring'''





     lowercase__   :       Dict				=	_single_underscore_re.split(SCREAMING_SNAKE_CASE_      )
     lowercase__   :       Any				=	[_multiple_underscores_re.split(SCREAMING_SNAKE_CASE_      ) for n in name]
     return "".join(n.capitalize() for n in itertools.chain.from_iterable(SCREAMING_SNAKE_CASE_      ) if n != ''      )

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   Tuple      ):



     '''simple docstring'''





     if os.path.basename(SCREAMING_SNAKE_CASE_      ) != name:
          raise ValueError(f"""Should be a dataset name, not a path: {name}"""      )
     return camelcase_to_snakecase(SCREAMING_SNAKE_CASE_      )

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   Dict     ,					SCREAMING_SNAKE_CASE_		:   str      ):



     '''simple docstring'''





     if os.path.basename(SCREAMING_SNAKE_CASE_      ) != name:
          raise ValueError(f"""Should be a dataset name, not a path: {name}"""      )
     if not re.match(_split_re     ,					SCREAMING_SNAKE_CASE_      ):
          raise ValueError(f"""Split name should match '{_split_re}'' but got '{split}'."""      )
     return f"""{filename_prefix_for_name(SCREAMING_SNAKE_CASE_      )}-{split}"""

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   List[Any]     ,					SCREAMING_SNAKE_CASE_		:   Dict     ,					SCREAMING_SNAKE_CASE_		:   Any     ,					SCREAMING_SNAKE_CASE_		:   Optional[int]=None      ):



     '''simple docstring'''





     lowercase__   :       Optional[Any]				=	filename_prefix_for_split(SCREAMING_SNAKE_CASE_     ,					SCREAMING_SNAKE_CASE_      )
     if filetype_suffix:
          prefix += f""".{filetype_suffix}"""
     lowercase__   :       Dict				=	os.path.join(SCREAMING_SNAKE_CASE_     ,					SCREAMING_SNAKE_CASE_      )
     return f"""{filepath}*"""

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   List[str]     ,					SCREAMING_SNAKE_CASE_		:   List[Any]     ,					SCREAMING_SNAKE_CASE_		:   str     ,					SCREAMING_SNAKE_CASE_		:   Dict=None     ,					SCREAMING_SNAKE_CASE_		:   Dict=None      ):



     '''simple docstring'''





     lowercase__   :       Optional[Any]				=	filename_prefix_for_split(SCREAMING_SNAKE_CASE_     ,					SCREAMING_SNAKE_CASE_      )
     lowercase__   :       str				=	os.path.join(SCREAMING_SNAKE_CASE_     ,					SCREAMING_SNAKE_CASE_      )

     if shard_lengths:
          lowercase__   :       List[str]				=	len(SCREAMING_SNAKE_CASE_      )
          lowercase__   :       Tuple				=	[f"""{prefix}-{shard_id:05d}-of-{num_shards:05d}""" for shard_id in range(SCREAMING_SNAKE_CASE_      )]
          if filetype_suffix:
               lowercase__   :       int				=	[filename + f""".{filetype_suffix}""" for filename in filenames]
          return filenames
     else:
          lowercase__   :       Any				=	prefix
          if filetype_suffix:
               filename += f""".{filetype_suffix}"""
          return [filename]




import math
import sys

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   int      ):



     '''simple docstring'''





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


if __name__ == "__main__":
       import doctest

       doctest.testmod()

