






"""simple docstring"""


def 					UpperCAmelCase			(				a__   ):





						'''simple docstring'''






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


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







"""simple docstring"""


from .number_theory.prime_numbers import next_prime




class 	__UpperCamelCase    :
					def __init__(       self       :  List[str]    ,   UpperCAmelCase       :  int    ,   UpperCAmelCase       :  int | None = None    ,   UpperCAmelCase       :  float | None = None    ,   )  ->					None:
											lowerCAmelCase      :Tuple				  = size_table
											lowerCAmelCase      :List[Any]				  = [None] * self.size_table
											lowerCAmelCase      :Tuple				  = 0.7_5 if lim_charge is None else lim_charge
											lowerCAmelCase      :str				  = 1 if charge_factor is None else charge_factor
											lowerCAmelCase      :list				  = []
											lowerCAmelCase      :dict				  = {}
					def 					UpperCAmelCase__   (       self       :  Optional[int]      )  ->					Union[str, Any]:
											return self._keys
					def 					UpperCAmelCase__   (       self       :  Dict      )  ->					Optional[Any]:
											return sum(1 for slot in self.values if slot is not None      ) / (
											    self.size_table * self.charge_factor
											)
					def 					UpperCAmelCase__   (       self       :  Any    ,   UpperCAmelCase       :  List[str]      )  ->					int:
											return key % self.size_table
					def 					UpperCAmelCase__   (       self       :  Dict    ,   UpperCAmelCase       :  Union[str, Any]      )  ->					int:
											print(f"""step {step_ord}"""      )
											print(list(range(len(self.values      )      )      )      )
											print(self.values      )
					def 					UpperCAmelCase__   (       self       :  Any    ,   UpperCAmelCase       :  Dict      )  ->					Any:
											lowerCAmelCase      :List[str]				  = 1
											lowerCAmelCase      :Union[str, Any]				  = values
											for value in values:
																	self.insert_data(UpperCAmelCase      )
																	self._step_by_step(UpperCAmelCase      )
																	i += 1
					def 					UpperCAmelCase__   (       self       :  str    ,   UpperCAmelCase       :  Dict    ,   UpperCAmelCase       :  Union[str, Any]      )  ->					Optional[Any]:
											lowerCAmelCase      :List[Any]				  = data
											lowerCAmelCase      :str				  = data
					def 					UpperCAmelCase__   (       self       :  Optional[int]    ,   UpperCAmelCase       :  str    ,   UpperCAmelCase       :  str=None      )  ->					Tuple:
											lowerCAmelCase      :Optional[Any]				  = self.hash_function(key + 1      )

											while self.values[new_key] is not None and self.values[new_key] != key:
																	if self.values.count(UpperCAmelCase      ) > 0:
																							lowerCAmelCase      :Tuple				  = self.hash_function(new_key + 1      )
																	else:
																							lowerCAmelCase      :Union[str, Any]				  = None
																							break

											return new_key
					def 					UpperCAmelCase__   (       self       :  Any      )  ->					Any:
											lowerCAmelCase      :Optional[Any]				  = [value for value in self.values if value is not None]
											lowerCAmelCase      :List[str]				  = next_prime(self.size_table    ,   factor=2      )
											self._keys.clear()
											lowerCAmelCase      :int				  = [None] * self.size_table  # hell's pointers D: don't DRY ;/
											for value in survivor_values:
																	self.insert_data(UpperCAmelCase      )
					def 					UpperCAmelCase__   (       self       :  Optional[int]    ,   UpperCAmelCase       :  Tuple      )  ->					int:
											lowerCAmelCase      :Union[str, Any]				  = self.hash_function(UpperCAmelCase      )

											if self.values[key] is None:
																	self._set_value(UpperCAmelCase    ,   UpperCAmelCase      )

											elif self.values[key] == data:
																	pass

											else:
																	lowerCAmelCase      :Tuple				  = self._collision_resolution(UpperCAmelCase    ,   UpperCAmelCase      )
																	if collision_resolution is not None:
																							self._set_value(UpperCAmelCase    ,   UpperCAmelCase      )
																	else:
																							self.rehashing()
																							self.insert_data(UpperCAmelCase      )