#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <vector>

using namespace std;

const int maxn =;

int dp[maxn][maxn];

char str[maxn];

void inti(int n){

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

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

       dp[i][j]=j-i+;

}

bool cmp(int s, int t, int num, int n){

    for(int i=; i<num; ++i)

         if(str[s+i]!=str[t+i]||t+i>=n) return false;

    return true;

}

int ccc(int v){

   int ans=;

   while(v>) {

     ans++;

     v/=;

   }

   return ans;

}

int main()

{

     int cas;

     scanf("%d",&cas);

     for(int cc=; cc<=cas; ++cc){

          scanf("%s",str);

          int n=strlen(str);

          int ok=;

          inti(n);

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

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

                   ok=;

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

                        if(cmp(j,k,i,n)==true) ok++;

                        else break;

                   }

                   for(int k=; k<i-; ++k)

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

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

                   dp[j][j+i*(ok+)-] =min(dp[j][j+i*(ok+) - ] ,dp[j][j+i-]++ccc(ok+) );

              }

          }

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

              for(int j=; j+i-<n; ++j)

                 for(int k=; k<i-; ++k)

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

          }

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

     }

    return ;

}