We say a sequence of char- acters is a palindrome if it is the same written forwards and backwards. For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not.

A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups.

Given a sequence of charac- ters, we can always create a par- tition of these characters such that each group in the partition is a palindrome! Given this ob- servation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palin- drome?

For example:

• ‘racecar’ is already a palindrome, therefore it can be partitioned into one group.

• ‘fastcar’ does not con- tain any non-trivial palin- dromes, so it must be par- titioned as (‘f’, ‘a’, ‘s’, ‘t’, ‘c’, ‘a’, ‘r’).

• ‘aaadbccb’ can be parti- tioned as (‘aaa’, ‘d’, ‘bccb’).

  Input

Can you read upside-down?

Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.

Output

For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.

Sample Input

3

racecar

fastcar

aaadbccb

Sample Output

1 7 3

最少回文划分

f[i]表示到i的最少次数，随便一转移

判断回文：p[i][j]=p[i+1][j-1] if s[i]==s[j]

//

//  main.cpp

//  uva11584

//

//  Created by Candy on 10/18/16.

//  Copyright © 2016 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int T,n;

char s[N];

int f[N],p[N][N];

bool pal(int l,int r){

    if(l>=r) return ;

    if(p[l][r]!=-) return p[l][r];

    if(s[l]==s[r]) p[l][r]=pal(l+,r-);

    else p[l][r]=;

    return p[l][r];

}

void dp(){

    memset(p,-,sizeof(p));

    f[]=;f[]=;

    for(int i=;i<=n;i++){

        f[i]=INF;

        for(int j=;j<i;j++)

            if(pal(j+,i)) f[i]=min(f[i],f[j]+);

    }

}

int main(int argc, const char * argv[]) {

    T=read();

    while(T--){

        scanf("%s",s+);

        n=strlen(s+);

        dp();

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

    }

    return ;

}