'''simple docstring'''




from __future__ import annotations






def __lowerCAmelCase				(							UpperCamelCase__       )			->					set[int]:
				__lowerCamelCase						=						{1}
				__lowerCamelCase						=						[1]
				for _ in range(2       ,						depth + 1       ):
								__lowerCamelCase						=						[*previous_coefficients, 0]
								__lowerCamelCase						=						[0, *previous_coefficients]
								__lowerCamelCase						=						[]
								for x, y in zip(UpperCamelCase__       ,						UpperCamelCase__       ):
												coefficients.add(x + y       )
												previous_coefficients.append(x + y       )
				return coefficients






def __lowerCAmelCase				(							UpperCamelCase__       )			->					set[int]:
				__lowerCamelCase						=						set()
				for number in unique_coefficients:
								__lowerCamelCase						=						2
								__lowerCamelCase						=						number
								while divisor**2 <= copy_number:
												__lowerCamelCase						=						0
												while copy_number % divisor == 0:
																copy_number //= divisor
																multiplicity += 1
												if multiplicity >= 2:
																non_squarefrees.add(UpperCamelCase__       )
																break
												divisor += 1

				return unique_coefficients.difference(UpperCamelCase__       )






def __lowerCAmelCase				(							UpperCamelCase__ = 51       )			->					int:
				__lowerCamelCase						=						get_pascal_triangle_unique_coefficients(UpperCamelCase__       )
				__lowerCamelCase						=						get_squarefrees(UpperCamelCase__       )
				return sum(UpperCamelCase__       )


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

'''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}')
