#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 2e6 + 10;

char a[N], s[N];

int dp[N], c[N], d[N], f[N], g[N];

int T, n, m, r, p, cnt, ans, now, ca = 0;

vector <int> v[N];

void up(int &x, int y){ if (x < y) x = y;}

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%s", a + 1);

		n = strlen(a + 1);

		rep(i, 1, n) s[i << 1] = a[i], s[i << 1 | 1] = '#';

		s[0] = '$', s[1] = '#', s[m = (n + 1) << 1] = '@';

		r = 0, p = 0, f[1] = 1;

		rep(i, 2, m - 1){

			for (f[i] = r > i ? min(r - i, f[p * 2 - i]) : 1; s[i - f[i]] == s[i + f[i]]; f[i]++);

			if (i + f[i] > r) r = i + f[i], p = i;

		}

		rep(i, 0, m) g[i] = 0;

		rep(i, 2, m - 1) up(g[i - f[i] + 1], i + 1);

		rep(i, 1, m) up(g[i], g[i - 1]);

		ans = 0; cnt = 0;

		for (int i = 2; i < m; i += 2){

			++cnt;

			c[cnt] = g[i] - i;

		}

		rep(i, 1, n) c[i] = i + c[i] - 1;

		rep(i, 1, n) d[i] = i;

		rep(i, 1, n) d[c[i]] = min(d[c[i]], i);

		dec(i, n - 1, 1) d[i] = min(d[i], d[i + 1]);

		rep(i, 0, n + 1) dp[i] = 1e9; dp[0] = 0;

		rep(i, 1, n) dp[i] = min(dp[i], dp[d[i] - 1] + 1);

		printf("Case #%d: %d\n", ++ca, dp[n]);

	}

	return 0;

}