#include<stdio.h>
//#include<string.h>

short s[5001][5001];
char str[5001];
//char temp[5001];
/*
int f(int n)
{
	int i,j;
//	for(i=n-1,j=0;i>=0;j++,i--)
//		temp[j]=str[i];
	for(i=0;i<n;i++)
		s[0][i]=0;
	for(i=0;i<n;i++)
		s[i][0]=0;
//	temp[n]='\0';
//	puts(temp);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(str[i-1]==str[n-j])
				s[i][j]=s[i-1][j-1]+1;
			else
				s[i][j]=s[i-1][j]>s[i][j-1]?s[i-1][j]:s[i][j-1];
		//	printf("%d ",s[i][j]);
		
		}
	//	printf("\n");
	}
	return n-s[n][n];
}
*/