





def    UpperCAmelCase				(  _lowerCamelCase   :	str  ):





						'''simple docstring'''


						SCREAMING_SNAKE_CASE__  :					Optional[int] =       len(_lowerCamelCase  )
						SCREAMING_SNAKE_CASE__  :					Any =       [0] * length
						SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       [[False for i in range(_lowerCamelCase  )] for j in range(_lowerCamelCase  )]
						for i, c in enumerate(_lowerCamelCase  ):
												SCREAMING_SNAKE_CASE__  :					Optional[Any] =       i
												for j in range(i + 1  ):
																		if c == string[j] and (i - j < 2 or is_palindromic[j + 1][i - 1]):
																								SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       True
																								SCREAMING_SNAKE_CASE__  :					Optional[int] =       min(_lowerCamelCase      , 0 if j == 0 else (cut[j - 1] + 1)  )
												SCREAMING_SNAKE_CASE__  :					str =       mincut
						return cut[length - 1]


if __name__ == "__main__":
				__lowercase							:Optional[Any]							=	input("Enter the string: ").strip()
				__lowercase							:Union[str, Any]							=	find_minimum_partitions(s)
				print(f"Minimum number of partitions required for the '{s}' is {ans}")






from itertools import combinations_with_replacement







def    UpperCAmelCase				(  _lowerCamelCase   :	int = 100  ):





						'''simple docstring'''


						SCREAMING_SNAKE_CASE__  :					list[int] =       [*list(range(1      , 21  )  ), 25]
						SCREAMING_SNAKE_CASE__  :					list[int] =       [2 * x for x in range(1      , 21  )] + [50]
						SCREAMING_SNAKE_CASE__  :					list[int] =       [3 * x for x in range(1      , 21  )]
						SCREAMING_SNAKE_CASE__  :					list[int] =       singles + doubles + triples + [0]

						SCREAMING_SNAKE_CASE__  :					int =       0
						SCREAMING_SNAKE_CASE__  :					int
						SCREAMING_SNAKE_CASE__  :					int
						SCREAMING_SNAKE_CASE__  :					int
						SCREAMING_SNAKE_CASE__  :					int

						for double in doubles:
												for throwa, throwa in combinations_with_replacement(_lowerCamelCase      , 2  ):
																		SCREAMING_SNAKE_CASE__  :					int =       double + throwa + throwa
																		if checkout_total < limit:
																								num_checkouts += 1

						return num_checkouts


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