#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int dp[1010];

void f(int k, string z, string x, int kk) {
	int i, j, n = x.length();
	for(i = 1; i <= n; ++i) {
		if(n%i == 0) {
			string q = x.substr(0, i), p = "";
			for(j = 0; j < n/i; ++j)
				p += q;
			if (p == x) {
				if(i <= z.length() and z.find(q) != string::npos)
					dp[k] = min(dp[k], dp[kk-1] + 1 + n/i);
			}
		}
	}
}

int main() {
	int t, i, j, tc = 0, n;
	cin >> t;
	while(t--) {
		tc++;
		cout << "Case #" << tc << ": ";
		string s;
		cin >> s;
		n = s.length();
		dp[0] = 1;
		dp[1] = 2;
		for(i = 2; i < n; ++i) {
			dp[i] = dp[i-1] + 1;
			string x = "";
			x += s[i];
			for(j = i - 1; j >= 1; --j) {
				x = s[j] + x;
				// cout << i << " " << j << endl;
				string z = s.substr(0, j);
				f(i, z, x, j);
			}
			// cout << dp[i] << endl;
		}
		cout << dp[n-1] << endl;
	}
	return 0;
}