这题就没什么好说的了。直接枚举2 ^ 16 的状态，用1表示拿这位，0表示不拿，每次判断是否可以这么拿。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#include <iomanip>

#define PI acos(-1.0)

#define Max 2505

#define inf 2000000000

#define LL(x) ( x << 1 )

#define RR(x) ( x << 1 | 1 )

#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

#define mp(a,b) make_pair(a,b)

#define PII pair<int,int>

using namespace std;

inline void RD(int &ret) {

    char c;

    do {

        c = getchar();

    } while(c < '0' || c > '9') ;

    ret = c - '0';

    while((c=getchar()) >= '0' && c <= '9')

        ret = ret * 10 + ( c - '0' );

}

inline void OT(int a) {

    if(a >= 10)OT(a / 10) ;

    putchar(a % 10 + '0') ;

}

int is[20] ;

int MV[1 << 17] ;

int dp[1 << 17] ;

char a[20] ;

int main() {

    int  t ;

    cin >> t ;

    while( t -- ) {

        cin >> a ;

        int l = strlen(a) ;

        dp[0] = 0 ;

        for (int i = 1 ; i < (1 << l ) ; i ++ ){

            int aa = i ;

            int num = 0 ;

            for (int j = 0 ; j < l ; j ++ ){

                if((aa >> j) & 1){

                    is[num ++ ] = (int)a[j] ;

                }

            }

            bool flag = 0 ;

            for (int j = 0 ; j < num / 2 ; j ++ ){

                if(is[j] != is[num - j - 1]){

                    flag = 1 ;

                    break ;

                }

            }

            if(!flag)MV[i] = 1 ;

            else MV[i] = 0 ;

        }

        for (int i = 1 ; i < (1 << l) ; i ++ ){

            if(MV[i])dp[i] = dp[0] + 1 ;

            else dp[i] = inf ;

            for (int j = i ; j > 0 ; -- j &= i){//这个操作是看标程的，一开始我在这里T了几发。

                if(MV[j]){

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

                }

            }

        }

        cout << dp[(1 << l ) - 1] << endl;

    }

    return 0 ;

}