
"""simple docstring"""




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


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


"""simple docstring"""




from functools import lru_cache

@lru_cache
def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_			):
					if not isinstance(SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			):
										raise TypeError('k must be an integer.'			)
					if k < 0:
										raise ValueError('k integer must be greater or equal to zero.'			)
					if k == 0:
										return 0
					elif k == 1:
										return 1
					else:
										return fibonacci(k - 1			) + fibonacci(k - 2			)

def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			):
					SCREAMING_SNAKE_CASE				=	len(SCREAMING_SNAKE_CASE_			)
					# Find m such that F_m >= n where F_i is the i_th fibonacci number.
					SCREAMING_SNAKE_CASE				=	0
					while True:
										if fibonacci(SCREAMING_SNAKE_CASE_			) >= len_list:
															SCREAMING_SNAKE_CASE				=	i
															break
										i += 1
					SCREAMING_SNAKE_CASE				=	0
					while fibb_k > 0:
										SCREAMING_SNAKE_CASE				=	min(
										    offset + fibonacci(fibb_k - 1			),     len_list - 1			)  # Prevent out of range
										SCREAMING_SNAKE_CASE				=	arr[index_k]
										if item_k_1 == val:
															return index_k
										elif val < item_k_1:
															fibb_k -= 1
										elif val > item_k_1:
															offset += fibonacci(fibb_k - 1			)
															fibb_k -= 2
					else:
										return -1


if __name__ == "__main__":
	import doctest

	doctest.testmod()
