import java.io.*;
import java.util.*;

public class StringCompression {
	//----------------------------------------------------------------------

	private static final Scanner cin = new Scanner(System.in);
	private static final int N = 200;

	//----------------------------------------------------------------------

	private static int compress(String s) {
		int n = s.length();

		boolean[][] rep = new boolean[n][n];
		{
			for(int i = 1; i < n; i++) {
				for(int j = i; j + i <= n; j++) {
					rep[j][i] = s.substring(j-i,j).equals(s.substring(j,j+i));
				}
			}
		}

		int[] num = new int[N+1];
		{
			int j = 1;
			int k = 0;

			for(int i = 1; i <= N; i++) {
				if(i == j) { k += 1; j *= 10; }
				num[i] = k;
			}
		}

		// CYK-style algorithm
		int[][] len = new int[n+1][n+1];
		int[][] fee = new int[n+1][n+1];
		{
			for(int i = 0; i < n; i++) {
				len[i][1] = 1;
				fee[i][1] = 1;
			}

			for(int i = 2; i <= n; i++) {
				for(int j = 0; j + i <= n; j++) {
					len[j][i] = i;
					fee[j][i] = i;

					for(int k = 1; k <= i - 1; k++) {
						int len1, fee1;

						if(len[j][k] == i - k && rep[j+k][i-k]) {
							// compress
							len1 = i - k;
							fee1 = fee[j+k][i-k] + num[i / (i - k)] + 2;
							fee1 = Math.min(i, fee1);
						}
						else {
							// concat
							len1 = i;
							fee1 = fee[j][k] + fee[j+k][i-k];
						}

						if(fee[j][i] > fee1 ||
						   fee[j][i] == fee1 && len[j][i] > len1) {
							len[j][i] = len1;
							fee[j][i] = fee1;
						}
					}
				}
			}
		}

		return fee[0][n];
	}

	//----------------------------------------------------------------------

	public static void main(String[] args) {
		int n = cin.nextInt();

		for(int i = 0; i < n; i++) {
			System.out.println( compress(cin.next()) );
		}
	}

	//----------------------------------------------------------------------
}