/**

题目：hihoCoder #1320 : 压缩字符串

链接：https://hihocoder.com/problemset/problem/1320

描述

小Hi希望压缩一个只包含大写字母'A'-'Z'的字符串。他使用的方法是：如果某个子串 S 连续出现了 X 次，就用'X(S)'来表示。

例如AAAAAAAAAABABABCCD可以用10(A)2(BA)B2(C)D表示。

此外，这种压缩方法是可以嵌套的，例如HIHOHIHOCODERHIHOHIHOCODER可以表示成2(2(HIHO)CODER)。

对于一个字符串 S ，合法的压缩表示可能有很多种。例如AAAAAAAAAABABABCCD还可以表示成9(A)3(AB)CCD。

小Hi希望知道其中最短的表示方法长度是多少。

输入

第一行一个正整数 T (1 ≤ T ≤ 10)，表示测试数据的组数。

以下 T 行每行一个字符串 S ，长度不超过100。

输出

对于每组数据，输出最短的表示方法的长度。

思路：区间dp，定义dp[i][j]表示区间[i,j]压缩最小长度。

终止条件，容易推得长度<=4的区间最短长度就是区间长度。

如果长度>4.那么如果当前字符串是周期字符串，那么显然是可以合并越多越好，即：如果全部都是相同的，那么就全部合并起来。

所以从区间长度的约数由小到大找满足的周期。然后合并。

如果找不到，那么切割成两部分。

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<cctype>

#include<set>

#include<cstring>

#include<cmath>

using namespace std;

typedef pair<int,int> P;

typedef long long LL;

const int N = ;

const int mod = ;

const int INF = 0x3f3f3f3f;

int dp[N][N];

char s[N];

vector<int> v[N];

void init()

{

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

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

            if(i%j==){

                v[i].push_back(j);

            }

        }

    }

}

bool cmp(int l,int r,int l2,int r2)

{

    for(int i = l, j = l2; i < r; i++, j++){

        if(s[i]!=s[j]) return false;

    }

    return true;

}

int getLen(int x)

{

    int cnt = ;

    while(x){

        x/=; cnt++;

    }

    return cnt;

}

int dfs(int l,int r)

{

    if(r-l+<=) return r-l+;

    int &res = dp[l][r];

    if(~res) return res;

    int len = r-l+;

    int n = v[len].size();

    for(int i = ; i < n; i++){///划分段数

        int d = v[len][i];     ///S = [l,l+d);

        int j;

        for(j = l+d; j <= r; j+=d){///T = [l+d,l+2d);

            if(cmp(l,l+d,j,j+d)==false) break;///不匹配。

        }

        if(j>r){

            return res = getLen(len/d)++dfs(l,l+d-);

        }

    }

    res = INF;

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

        res = min(res,dfs(l,i)+dfs(i+,r));

    }

    return res;

}

int main()

{

    int T;

    init();

    cin>>T;

    while(T--)

    {

        scanf("%s",s);

        memset(dp, -, sizeof dp);

        printf("%d\n",dfs(,strlen(s)-));

    }

    return ;

}