#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define se second
#define fs first
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define ll long long

const int maxn = 205;
int dp[ maxn ][ maxn ];
int T;
char S[ maxn ];

bool judge( int s, int e, int l )
{
    for( int i = s + l; i <= e; i ++ )
    {
        int k = ( i - s ) / l;
        if( S[ i - 1 ] != S[ i - k * l - 1 ] ) return false;
    }
    return true;
}

int num_length( int x )
{
    int l = 0;
    while( x )
    {
        l ++;
        x /= 10;
    }
    return l;
}

int main()
{
    scanf( "%d", &T );
    while( T -- )
    {
        scanf( "%s", S );
        int n = strlen( S );
        for( int i = 1; i <= n; i ++ ) dp[ i ][ i ] = 1;
        for( int k = 2; k <= n; k ++ )
        {
            for( int i = 1; i + k - 1 <= n; i ++ )
            {
                int j = i + k - 1;
                dp[ i ][ j ] = k;
                for( int p = i; p <= j - 1; p ++ ) dp[ i ][ j ] = min( dp[ i ][ j ], dp[ i ][ p ] + dp[ p + 1 ][ j ] );
                for( int p = 1; p <= k / 2; p ++ )
                {
                    if( k % p ) continue;
                    if( judge( i, j, p ) )
                    {
                        int num = k / p;
                        dp[ i ][ j ] = min( dp[ i ][ j ], 2 + dp[ i ][ i + p - 1 ] + num_length( num ) );
                    }
                }
            }
        }
        printf( "%d\n", dp[ 1 ][ n ] );
    }
    return 0;
}