#include<set>

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 16 + 5;

const int M = maxn * 30;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 1e4 + 7;

char s[maxn];

int pa[1 << maxn];

int dp[1 << maxn];

int n, cnt;

bool check(int st){

    char tmp[20];

    int len = 0;

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

        if(st & (1 << i)){

            tmp[++len] = s[i];

        }

    }

    for(int i = 1; i <= len / 2; i++){

        if(tmp[i] != tmp[len - i + 1]) return false;

    }

    return true;

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        scanf("%s", &s);

        n = strlen(s);

        cnt = 0;

        memset(dp, INF, sizeof(dp));

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

            if(check(i)){

                pa[cnt++] = i;

                dp[i] = 1;

            }

        }

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

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

                if(i & pa[j]) continue;

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

            }

        }

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

    }

    return 0;

}