






import unittest
from timeit import timeit







def 		_UpperCamelCase      (			UpperCamelCase_				:    int			,				UpperCamelCase_				:    int						)     ->      int:

						"""simple docstring"""



						lowerCAmelCase__			  =  first_num if first_num >= second_num else second_num
						lowerCAmelCase__			  =  max_num
						while (common_mult % first_num > 0) or (common_mult % second_num > 0):
												common_mult += max_num
						return common_mult







def 		_UpperCamelCase      (			UpperCamelCase_				:    int			,				UpperCamelCase_				:    int						)     ->      int:

						"""simple docstring"""



						return b if a == 0 else greatest_common_divisor(b % a			,				UpperCamelCase_						)







def 		_UpperCamelCase      (			UpperCamelCase_				:    int			,				UpperCamelCase_				:    int						)     ->      int:

						"""simple docstring"""



						return first_num // greatest_common_divisor(UpperCamelCase_			,				UpperCamelCase_						) * second_num







def 		_UpperCamelCase      (			)     ->      str:

						"""simple docstring"""



						lowerCAmelCase__			  =  (
						    'from __main__ import least_common_multiple_slow, least_common_multiple_fast'
						)
						print(
						    'least_common_multiple_slow():'			,				timeit('least_common_multiple_slow(1000, 999)'			,				setup=UpperCamelCase_						)			,				)
						print(
						    'least_common_multiple_fast():'			,				timeit('least_common_multiple_fast(1000, 999)'			,				setup=UpperCamelCase_						)			,				)


class 			__SCREAMING_SNAKE_CASE    (      unittest.TestCase):
						_SCREAMING_SNAKE_CASE		:				Optional[Any]            =    (
						    (10, 20),
						    (13, 15),
						    (4, 31),
						    (10, 42),
						    (43, 34),
						    (5, 12),
						    (12, 25),
						    (10, 25),
						    (6, 9),
						)
						_SCREAMING_SNAKE_CASE		:				Any            =    (20, 195, 124, 210, 1462, 60, 300, 50, 18)






						def 					UpperCamelCase__					(		self      ):






												"""simple docstring"""
												for i, (first_num, second_num) in enumerate(self.test_inputs      ):
																		lowerCAmelCase__			  =  least_common_multiple_slow(_UpperCamelCase   ,  _UpperCamelCase      )
																		lowerCAmelCase__			  =  least_common_multiple_fast(_UpperCamelCase   ,  _UpperCamelCase      )
																		with self.subTest(i=_UpperCamelCase      ):
																								self.assertEqual(_UpperCamelCase   ,  self.expected_results[i]      )
																								self.assertEqual(_UpperCamelCase   ,  self.expected_results[i]      )


if __name__ == "__main__":
					benchmark()
					unittest.main()













def 		_UpperCamelCase      (			UpperCamelCase_				:    str						)     ->      int:

						"""simple docstring"""



						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__":
					__snake_case			:			Optional[Any]			   =   input("""Enter the string: """).strip()
					__snake_case			:			List[Any]			   =   find_minimum_partitions(s)
					print(f'Minimum number of partitions required for the \'{s}\' is {ans}')





