_SCREAMING_SNAKE_CASE:    List[Any]     						=							{
    '''0''': 1,
    '''1''': 1,
    '''2''': 2,
    '''3''': 6,
    '''4''': 24,
    '''5''': 120,
    '''6''': 720,
    '''7''': 5_040,
    '''8''': 40_320,
    '''9''': 362_880,
}

_SCREAMING_SNAKE_CASE:    Dict     						=							{145: 145}

_SCREAMING_SNAKE_CASE:    Any     						=							{
    145: 0,
    169: 3,
    36_301: 3,
    1_454: 3,
    871: 2,
    45_361: 2,
    872: 2,
}






def  UpperCAmelCase__(    lowerCamelCase_	):



			"""simple docstring"""





			if n in CACHE_SUM_DIGIT_FACTORIALS:
						return CACHE_SUM_DIGIT_FACTORIALS[n]
			_snake_case														=   sum(DIGIT_FACTORIALS[let] for let in str(lowerCamelCase_	)	)
			_snake_case														=   ret
			return ret






def  UpperCAmelCase__(    lowerCamelCase_				,						lowerCamelCase_ = None	):



			"""simple docstring"""





			_snake_case														=   previous or set()
			if n in CHAIN_LENGTH_CACHE:
						return CHAIN_LENGTH_CACHE[n]
			_snake_case														=   sum_digit_factorials(lowerCamelCase_	)
			if next_number in previous:
						_snake_case														=   0
						return 0
			else:
						previous.add(lowerCamelCase_	)
						_snake_case														=   1 + chain_length(lowerCamelCase_				,						lowerCamelCase_	)
						_snake_case														=   ret
						return ret






def  UpperCAmelCase__(    lowerCamelCase_ = 60				,						lowerCamelCase_ = 1000000	):



			"""simple docstring"""





			return sum(1 for i in range(1				,						lowerCamelCase_	) if chain_length(lowerCamelCase_	) == num_terms	)


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


def  UpperCAmelCase__(    lowerCamelCase_	):



			"""simple docstring"""





			_snake_case														=   len(lowerCamelCase_	)
			_snake_case														=   [0] * length
			_snake_case														=   [[False for i in range(lowerCamelCase_	)] for j in range(lowerCamelCase_	)]
			for i, c in enumerate(lowerCamelCase_	):
						_snake_case														=   i
						for j in range(i + 1	):
									if c == string[j] and (i - j < 2 or is_palindromic[j + 1][i - 1]):
												_snake_case														=   True
												_snake_case														=   min(lowerCamelCase_				,						0 if j == 0 else (cut[j - 1] + 1)	)
						_snake_case														=   mincut
			return cut[length - 1]


if __name__ == "__main__":
			_SCREAMING_SNAKE_CASE:    Dict     						=							input('''Enter the string: ''').strip()
			_SCREAMING_SNAKE_CASE:    str     						=							find_minimum_partitions(s)
			print(F"Minimum number of partitions required for the '{s}' is {ans}")

