Description

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。

Input

输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

Output

仅一行，包含一个数，即最少的涂色次数。

Sample Input

Sample Output

【样例输入1】

AAAAA

【样例输入1】

RGBGR

【样例输出1】

【样例输出1】

HINT

%的数据满足：<=n<=

%的数据满足：<=n<=

Source

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

char s[];

int dp[][];

int main()

{

    scanf("%s",s + );

    int n = strlen(s + );

    memset(dp,,sizeof(dp));

//    cout<<n<<endl;

    duke(i,,n)

    {

        dp[i][i] = ;

    }

    duke(l,,n - )

    {

        duke(i,,n)

        {

            int j = i + l;

            if(j > n)

            break;

            if(s[i] == s[j])

            {

                if(l == )

                dp[i][j] = ;

                else

                {

                    dp[i][j] = min(dp[i + ][j],min(dp[i][j - ],dp[i + ][j - ] + ));

                }

            }

            else

            {

                duke(k,i,j - )

                {

                    dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + ][j]);

                }

            }

        }

    }

    printf("%d\n",dp[][n]);

    return ;

}