// memoization-version
//  (with very trivial input validation)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cctype>
using namespace std;

struct Solver
{
	Solver( const string& s )
		: data( s )
		, memo( data.size()+1, vector<int>( data.size()+1 ) ) {}

	// Original data
	string data;

	// Caluculate data[s,e)'s minimum compressed length, using memoization.
	vector< vector<int> > memo;
	int minimum( int s, int e )
	{
		if( memo[s][e] )
			return memo[s][e];

		// Pattern 0: No compression
		int result = e-s;

		// Pattern 1: divide into two distinct parts
		//            O(N) loop
		for(int k=s+1; k<=e-1; ++k)
			result = min( result, minimum(s,k)+minimum(k,e) );

		// Pattern 2: "data[s,e)" ==> "r(S)"
		//            O(number of divisors of e-s) loop
		//            # Max is 18 at e-s=180, so total complexitiy = 200*200*200*18
		//            #
		//            # I can add some more pruning to current implementation:
		//            #   - compare "result" and "digits+minimum(s,s+len)+2"
		//            #     before the !equal loop
		//            #   - compare "minimum(s,s+len)" and "minimum(i,i+len)"
		//            #     before testing !equal
		//            # Combining those two prunings may improve the worst case. (not sure)
		for(int r=2; r<=e-s; ++r)
			if( (e-s)%r == 0 )
			{
				// O(N) loop
				int len = (e-s)/r, digits;
				for(int i=s+len; i<e; i+=len)
					if( !equal(data.begin()+s, data.begin()+s+len, data.begin()+i) )
						goto Next_r;

				digits = r<10 ? 1 : r<100 ? 2 : 3;
				result = min( result, digits+minimum(s,s+len)+2 );
			Next_r:;
			}

		return memo[s][e] = result;
	}
};

int main()
{
	int T; cin >> T;
	while(T--)
	{
		// Input (all letters are lower case alphabets so getline is not necessary)
		string line; cin >> line;
		assert( 1<=line.size() && line.size()<=200 );
		for(int i=0; i!=line.size(); ++i) assert( islower(line[i]) );

		// Solve & Output
		cout << Solver(line).minimum(0, line.size()) << endl;
	}
}