




'''simple docstring'''





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


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





'''simple docstring'''

def  UpperCamelCase(	UpperCAmelCase_ = 1_00      ):
 UpperCAmelCase			:      Optional[Any]		   =					[[0 for _ in range(UpperCAmelCase_      )] for _ in range(m + 1      )]
 for i in range(m + 1      ):
  UpperCAmelCase			:      Optional[int]		   =					1

 for n in range(m + 1      ):
  for k in range(1    ,			UpperCAmelCase_      ):
   memo[n][k] += memo[n][k - 1]
   if n > k:
    memo[n][k] += memo[n - k - 1][k]

 return memo[m][m - 1] - 1


if __name__ == "__main__":
 print(solution(int(input("Enter a number: ").strip())))




