'''simple docstring'''




from __future__ import annotations

from typing import Generic, TypeVar

__UpperCAmelCase  							=TypeVar("T")




class 					a__   (     UpperCAmelCase__				):
     pass




class 					a__   (     UpperCAmelCase__				):
     pass




class 					a__   (     Generic[T]				):






     def __init__(				self	:	Optional[Any]						,       a	:	int = 10					):





         """simple docstring"""



         __lowerCamelCase						=						[]
         __lowerCamelCase						=						limit






     def __bool__(				self	:	int					):





         """simple docstring"""



         return bool(self.stack					)






     def __str__(				self	:	int					):





         """simple docstring"""



         return str(self.stack					)






     def      SCREAMING_SNAKE_CASE__     (				self	:	Union[str, Any]						,       a	:	T					):





         """simple docstring"""



         if len(self.stack					) >= self.limit:
             raise StackOverflowError
         self.stack.append(a					)






     def      SCREAMING_SNAKE_CASE__     (				self	:	int					):





         """simple docstring"""



         if not self.stack:
             raise StackUnderflowError
         return self.stack.pop()






     def      SCREAMING_SNAKE_CASE__     (				self	:	int					):





         """simple docstring"""



         if not self.stack:
             raise StackUnderflowError
         return self.stack[-1]






     def      SCREAMING_SNAKE_CASE__     (				self	:	Tuple					):





         """simple docstring"""



         return not bool(self.stack					)






     def      SCREAMING_SNAKE_CASE__     (				self	:	Optional[Any]					):





         """simple docstring"""



         return self.size() == self.limit






     def      SCREAMING_SNAKE_CASE__     (				self	:	Union[str, Any]					):





         """simple docstring"""



         return len(self.stack					)






     def __contains__(				self	:	Optional[int]						,       a	:	T					):





         """simple docstring"""



         return item in self.stack






def __lowerCAmelCase				(							)			->					None:
    __lowerCamelCase						=						Stack(10       )
    assert bool(UpperCamelCase__       ) is False
    assert stack.is_empty() is True
    assert stack.is_full() is False
    assert str(UpperCamelCase__       ) == "[]"

    try:
        __lowerCamelCase						=						stack.pop()
        raise AssertionError  # This should not happen
    except StackUnderflowError:
        assert True  # This should happen

    try:
        __lowerCamelCase						=						stack.peek()
        raise AssertionError  # This should not happen
    except StackUnderflowError:
        assert True  # This should happen

    for i in range(10       ):
        assert stack.size() == i
        stack.push(UpperCamelCase__       )

    assert bool(UpperCamelCase__       )
    assert not stack.is_empty()
    assert stack.is_full()
    assert str(UpperCamelCase__       ) == str(list(range(10       )       )       )
    assert stack.pop() == 9
    assert stack.peek() == 8

    stack.push(1_00       )
    assert str(UpperCamelCase__       ) == str([0, 1, 2, 3, 4, 5, 6, 7, 8, 1_00]       )

    try:
        stack.push(2_00       )
        raise AssertionError  # This should not happen
    except StackOverflowError:
        assert True  # This should happen

    assert not stack.is_empty()
    assert stack.size() == 10

    assert 5 in stack
    assert 55 not in stack


if __name__ == "__main__":
  test_stack()

'''simple docstring'''




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


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