"""simple docstring"""



def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  list[list[int]]		, __snake_case      :  list[list[int]]   ):





  '''simple docstring'''





  lowercase							   =	[]
  lowercase							   =	len(_lowerCamelCase   )
  for i in range(_lowerCamelCase   ):
    lowercase							   =	[]
    for j in range(_lowerCamelCase   ):
      lowercase							   =	0
      for k in range(_lowerCamelCase   ):
        lowercase							   =	val + matrix_a[i][k] * matrix_b[k][j]
      list_a.append(_lowerCamelCase   )
    matrix_c.append(_lowerCamelCase   )
  return matrix_c
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  int   ):





  '''simple docstring'''





  return [[int(row == column   ) for column in range(_lowerCamelCase   )] for row in range(_lowerCamelCase   )]
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  int   ):





  '''simple docstring'''





  if n <= 1:
    return n
  lowercase							   =	identity(2   )
  lowercase							   =	[[1, 1], [1, 0]]
  lowercase							   =	n - 1
  while n > 0:
    if n % 2 == 1:
      lowercase							   =	multiply(_lowerCamelCase		, _lowerCamelCase   )
    lowercase							   =	multiply(_lowerCamelCase		, _lowerCamelCase   )
    lowercase							   =	int(n / 2   )
  return res_matrix[0][0]
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  int   ):





  '''simple docstring'''





  if n <= 1:
    return n
  lowercase							   =	0
  lowercase							   =	1
  for _ in range(2		, n + 1   ):
    lowercase   ,					lowercase							   =	fiba, fiba + fiba
  return fiba
def 						_SCREAMING_SNAKE_CASE			(   ):





  '''simple docstring'''





  for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
    lowercase							   =	int(''.join(c for c in ordinal if c in '0123456789'   )   )  # 1000th --> 1000
    print(
        f'{ordinal} fibonacci number using matrix exponentiation is '
        f'{nth_fibonacci_matrix(_lowerCamelCase   )} and using bruteforce is '
        f'{nth_fibonacci_bruteforce(_lowerCamelCase   )}\n'   )
  # from timeit import timeit
  # print(timeit("nth_fibonacci_matrix(1000000)",
  #              "from main import nth_fibonacci_matrix", number=5))
  # print(timeit("nth_fibonacci_bruteforce(1000000)",
  #              "from main import nth_fibonacci_bruteforce", number=5))
  # 2.3342058970001744
  # 57.256506615000035


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()










"""simple docstring"""



def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  str   ):





  '''simple docstring'''





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


if __name__ == "__main__":
    _UpperCamelCase		:  List[Any]						=		input('Enter the string: ').strip()
    _UpperCamelCase		:  List[Any]						=		find_minimum_partitions(s)
    print(F'''Minimum number of partitions required for the \'{s}\' is {ans}''')


