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

3racecarfastcaraaadbccb

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=1005,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;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 1;    if(p[l][r]!=-1) return p[l][r];    if(s[l]==s[r]) p[l][r]=pal(l+1,r-1);    else p[l][r]=0;    return p[l][r];}void dp(){    memset(p,-1,sizeof(p));    f[0]=0;f[1]=1;    for(int i=2;i<=n;i++){        f[i]=INF;        for(int j=0;j<i;j++)            if(pal(j+1,i)) f[i]=min(f[i],f[j]+1);    }}int main(int argc, const char * argv[]) {    T=read();    while(T--){        scanf("%s",s+1);        n=strlen(s+1);        dp();        printf("%d\n",f[n]);    }    return 0;}