
def      __UpperCAmelCase    (  snake_case_							:		int				):



	'''simple docstring'''



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


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




'''simple docstring'''

from __future__ import annotations

import random
from collections.abc import Iterable
from typing import Any, Generic, TypeVar

_UpperCAmelCase					:			Any				     =					TypeVar("""T""", bound=bool)


class    a__					(			Generic[T]   ):







				"""simple docstring"""



				def __init__(self							,      __lowercase		):
										__lowerCAmelCase											=					value
										__lowerCAmelCase											=					None
										__lowerCAmelCase											=					None




				@property
				def        _snake_case	(self		):
										return self._value




				@staticmethod
				def        _snake_case	(__lowercase							,      __lowercase		):
										if not roota:
																return roota

										if not roota:
																return roota

										if roota.value > roota.value:
																__lowerCAmelCase							,       __lowerCAmelCase											=					roota, roota

										if random.choice([True, False]		):
																__lowerCAmelCase							,       __lowerCAmelCase											=					roota.right, roota.left

										__lowerCAmelCase											=					RandomizedHeapNode.merge(roota.left							,      __lowercase		)

										return roota


class    a__					(			Generic[T]   ):







				"""simple docstring"""



				def __init__(self							,      __lowercase = ()		):
										__lowerCAmelCase											=					None

										if data:
																for item in data:
																						self.insert(__lowercase		)




				def        _snake_case	(self							,      __lowercase		):
										__lowerCAmelCase											=					RandomizedHeapNode.merge(self._root							,      RandomizedHeapNode(__lowercase		)		)




				def        _snake_case	(self		):
										__lowerCAmelCase											=					self.top()

										if self._root is None:
																return None

										__lowerCAmelCase											=					RandomizedHeapNode.merge(self._root.left							,      self._root.right		)

										return result




				def        _snake_case	(self		):
										if not self._root:
																raise IndexError('''Can\'t get top element for the empty heap.'''		)
										return self._root.value




				def        _snake_case	(self		):
										__lowerCAmelCase											=					None




				def        _snake_case	(self		):
										__lowerCAmelCase											=					[]
										while self:
																result.append(self.pop()		)

										return result




				def __bool__(self		):
										return self._root is not None


if __name__ == "__main__":
	import doctest

	doctest.testmod()

