"""simple docstring"""



from functools import partial
from typing import Any, Callable, Dict, List, Type, TypeVar, Union, overload

import torch
import torch.nn as nn
import torch.types
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[Any]		, __snake_case      :  Optional[int]		, __snake_case      :  List[str]   ):





  '''simple docstring'''





  if not inplace:
    lowercase							   =	ma + ma
  else:
    ma += ma

  return ma
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Any		, __snake_case      :  Union[str, Any]   ):





  '''simple docstring'''





  lowercase							   =	-1 * len(__snake_case   )
  lowercase							   =	list(range(len(tensor.shape[:zero_index]   )   )   )
  return tensor.permute(first_inds + [zero_index + i for i in inds]   )
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Tuple		, __snake_case      :  List[Any]   ):





  '''simple docstring'''





  return t.reshape(t.shape[:-no_dims] + (-1,)   )
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[Any]		, __snake_case      :  Optional[int]		, __snake_case      :  Optional[Any]		, __snake_case      :  List[str] = 1e-4   ):





  '''simple docstring'''





  lowercase							   =	mask.expand(*value.shape   )
  return torch.sum(mask * value		, dim=__snake_case   ) / (eps + torch.sum(__snake_case		, dim=__snake_case   ))
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  str		, __snake_case      :  Any = 2.3125		, __snake_case      :  Tuple = 21.6875		, __snake_case      :  Dict = 64   ):





  '''simple docstring'''





  lowercase							   =	torch.linspace(__snake_case		, __snake_case		, no_bins - 1		, device=pts.device   )
  lowercase							   =	torch.sqrt(torch.sum((pts.unsqueeze(-2   ) - pts.unsqueeze(-3   )) ** 2		, dim=-1   )   )
  return torch.bucketize(__snake_case		, __snake_case   )
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Optional[Any]		, __snake_case      :  List[str]   ):





  '''simple docstring'''





  lowercase							   =	dicts[0]
  lowercase							   =	{}
  for k, v in first.items():
    lowercase							   =	[d[k] for d in dicts]
    if isinstance(__snake_case		, __snake_case   ):
      lowercase							   =	dict_multimap(__snake_case		, __snake_case   )
    else:
      lowercase							   =	fn(__snake_case   )

  return new_dict
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Union[str, Any]		, __snake_case      :  Dict   ):





  '''simple docstring'''





  lowercase							   =	v_bins.view(((1,) * len(x.shape   )) + (len(__snake_case   ),)   )
  lowercase							   =	x[..., None] - reshaped_bins
  lowercase							   =	torch.argmin(torch.abs(__snake_case   )		, dim=-1   )
  return nn.functional.one_hot(__snake_case		, num_classes=len(__snake_case   )   ).float()
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  str		, __snake_case      :  Optional[int]		, __snake_case      :  int = 0		, __snake_case      :  List[str] = 0   ):





  '''simple docstring'''





  lowercase							   =	[]
  for i, s in enumerate(data.shape[:no_batch_dims]   ):
    lowercase							   =	torch.arange(__snake_case   )
    lowercase							   =	r.view(*(*((1,) * i), -1, *((1,) * (len(inds.shape   ) - i - 1)))   )
    ranges.append(__snake_case   )

  lowercase							   =	[slice(__snake_case   ) for _ in range(len(data.shape   ) - no_batch_dims   )]
  lowercase							   =	inds
  ranges.extend(__snake_case   )
  # Matt note: Editing this to get around the behaviour of using a list as an array index changing
  # in recent Numpy versions
  return data[tuple(__snake_case   )]


_UpperCamelCase		:  Optional[int]						=		TypeVar('T')
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[Any]		, __snake_case      :  Dict		, __snake_case      :  Any   ):





  '''simple docstring'''





  lowercase							   =	{}
  for k, v in dic.items():
    if isinstance(__snake_case		, __snake_case   ):
      lowercase							   =	dict_map(__snake_case		, __snake_case		, __snake_case   )
    else:
      lowercase							   =	tree_map(__snake_case		, __snake_case		, __snake_case   )

  return new_dict
@overload
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Tuple		, __snake_case      :  List[Any]		, __snake_case      :  str   ):





  '''simple docstring'''





  ...
@overload
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[Any]		, __snake_case      :  List[str]		, __snake_case      :  str   ):





  '''simple docstring'''





  ...
@overload
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Any		, __snake_case      :  Optional[int]		, __snake_case      :  Optional[int]   ):





  '''simple docstring'''





  ...
@overload
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  Any		, __snake_case      :  Optional[int]		, __snake_case      :  Tuple   ):





  '''simple docstring'''





  ...
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[str]		, __snake_case      :  Any		, __snake_case      :  Union[str, Any]   ):





  '''simple docstring'''





  if isinstance(__snake_case		, __snake_case   ):
    return dict_map(__snake_case		, __snake_case		, __snake_case   )
  elif isinstance(__snake_case		, __snake_case   ):
    return [tree_map(__snake_case		, __snake_case		, __snake_case   ) for x in tree]
  elif isinstance(__snake_case		, __snake_case   ):
    return tuple(tree_map(__snake_case		, __snake_case		, __snake_case   ) for x in tree   )
  elif isinstance(__snake_case		, __snake_case   ):
    return fn(__snake_case   )
  else:
    print(type(__snake_case   )   )
    raise ValueError('Not supported'   )



_UpperCamelCase		:  Dict						=		partial(tree_map, leaf_type=torch.Tensor)










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


