#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<limits.h>
#include<float.h>
#include<utility>
using namespace std;
#define E 0.0000000001
#define EE 0.00000001
int table[256][256];
int DP[256][256];
int solve( int s, int e )
{
	if( s >= e ) return 0;
	if( DP[s][e] >= 0 )
		return DP[s][e];

	int r = solve( s, e - 1 ) + 1;
	for( int plen = 1; plen <= (e - s) / 2; plen ++ ){
		for( int k = 2; e - plen * k >= s && k <= table[e - plen][e] + 1; k ++ ){
//			printf( "%d - %d + %d - %d * %d\n", s, e - plen * k, e - plen, e, k );
			int s2 = solve( s, e - plen * k ) + solve( e - plen, e );
			//if( plen >= 2 )
			s2 += 2;
			if( k < 10 ) s2 ++;
			else if( k < 100 ) s2 += 2;
			else s2 += 3;
			r = min( r, s2 );
		}
	}
	DP[s][e] = r;
	return r;
}

int main( void )
{
	FILE *in = fopen( "string.in", "r" );
	if( in == NULL )
		return 0;

	int TT;
	fscanf( in,"%d", &TT );
	char str[1024];
	for( int C = 0; C < TT; C ++ ){
		fscanf( in, "%s", str );
		int n = strlen( str );

		for( int i = 0; i < n; i ++ ){
			for( int j = i + 1; j <= n; j ++ ){
				int plen = j - i;
				int k;
				for( k = i - 1; k >= 0; k -- )
					if( str[k] != str[i + (k - i + plen * 200) % plen] )
						break;
				int w = (i - 1 - k) / plen;
				table[i][j] = w;
			}
		}

		for( int i = 0; i <= n; i ++ )
			for( int j = 0; j <= n; j ++ )
				DP[i][j] = -1;
		printf( "%d\n", solve( 0, n ) );
	}
	fclose( in );
	return 0;
}