#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef long long int ll;
typedef vector< pair< int , int > > vii;
typedef vector< int > vi;
typedef vector< vi> vvi;
typedef vector< long long int > vll;
typedef pair< int , int > pii;
const ll INF = 1e18 ;
const int inf = 1e9 ;
const int MOD = 1e9 + 7 ;
const int nax = 1000000 + 10 ;
int n, arr[ nax] ;
string s;
bool is1( int a, int b, string s1)
{
int start = 0 ;
for ( int i = a; i <= b; i++ )
if ( s[ i] ! = s1[ start++ ] ) return false ;
return true ;
}
bool is( int cur, string s1)
{
int len = s1.length ( ) ;
int i = 0 , j = len - 1 ;
while ( j <= cur)
{
if ( is1( i, j, s1) )
return true ;
i++ , j++ ;
}
return false ;
}
map< pair< int , string> , int > dp;
int solve( int cur, string cip)
{
//cout << cur << " " << cip << endl;
if ( cur >= n - 1 ) return 0 ;
if ( dp.count ( mp( cur, cip) ) )
return dp[ mp( cur, cip) ] ;
int ans = 1 + solve( cur + 1 , cip) ;
string abhi = "" ;
for ( int j = cur + 1 ; j < n; j++ )
{
abhi + = s[ j] ;
if ( is( cur, abhi) && cip ! = abhi)
ans = min( ans, 2 + solve( cur + ( int ) abhi.length ( ) , abhi) ) ;
}
if ( cip.length ( ) > 0 )
{
int len = cip.length ( ) ;
if ( is1( cur + 1 , cur + len, cip) )
ans = min( ans, 1 + solve( cur + len, cip) ) ;
}
return dp[ mp( cur, cip) ] = ans;
}
int main( )
{
ios:: sync_with_stdio ( 0 ) ;
freopen ( "inp.in" , "r" , stdin ) ;
freopen ( "out.txt" , "w" , stdout ) ;
int t, tt = 0 ;
cin >> t;
while ( t-- )
{
dp.clear ( ) ;
tt++ ;
cin >> s;
n = s.length ( ) ;
string emp = "" ;
cout << "Case #" << tt << ": " << solve( - 1 , emp) << endl;
}
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAoKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwp0eXBlZGVmIHZlY3RvcjwgcGFpcjxpbnQsIGludD4gPiB2aWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPHZpPiB2dmk7CnR5cGVkZWYgdmVjdG9yPGxvbmcgbG9uZyBpbnQ+IHZsbDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBwaWk7Cgpjb25zdCBsbCBJTkYgPSAxZTE4Owpjb25zdCBpbnQgaW5mID0gMWU5Owpjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsKY29uc3QgaW50IG5heCA9IDEwMDAwMDAgKyAxMDsKCmludCBuLCBhcnJbbmF4XTsKc3RyaW5nIHM7Cgpib29sIGlzMShpbnQgYSwgaW50IGIsIHN0cmluZyBzMSkKewogICAgaW50IHN0YXJ0ID0gMDsKICAgIGZvcihpbnQgaSA9IGE7IGkgPD0gYjsgaSsrKQogICAgICAgIGlmKHNbaV0gIT0gczFbc3RhcnQrK10pIHJldHVybiBmYWxzZTsKICAgIHJldHVybiB0cnVlOwp9CmJvb2wgaXMoaW50IGN1ciwgc3RyaW5nIHMxKQp7CiAgICBpbnQgbGVuID0gczEubGVuZ3RoKCk7CiAgICBpbnQgaSA9IDAsIGogPSBsZW4gLSAxOwogICAgd2hpbGUoaiA8PSBjdXIpCiAgICB7CiAgICAgICAgaWYoaXMxKGksIGosIHMxKSkKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgaSsrLCBqKys7CiAgICB9CiAgICByZXR1cm4gZmFsc2U7Cn0KbWFwPCBwYWlyPGludCwgc3RyaW5nPiwgaW50PiBkcDsKCmludCBzb2x2ZShpbnQgY3VyLCBzdHJpbmcgY2lwKQp7CiAgICAvL2NvdXQgPDwgY3VyIDw8ICIgIiA8PCBjaXAgPDwgZW5kbDsKICAgIGlmKGN1ciA+PSBuIC0gMSkgcmV0dXJuIDA7CiAgICBpZihkcC5jb3VudChtcChjdXIsIGNpcCkpKQogICAgICAgIHJldHVybiBkcFttcChjdXIsIGNpcCldOwogICAgaW50IGFucyA9IDEgKyBzb2x2ZShjdXIgKyAxLCBjaXApOwogICAgc3RyaW5nIGFiaGkgPSAiIjsKICAgIGZvcihpbnQgaiA9IGN1ciArIDE7IGogPCBuOyBqKyspCiAgICB7CiAgICAgICAgYWJoaSArPSBzW2pdOwogICAgICAgIGlmKGlzKGN1ciwgYWJoaSkgJiYgY2lwICE9IGFiaGkpCiAgICAgICAgICAgIGFucyA9IG1pbihhbnMsIDIgKyBzb2x2ZShjdXIgKyAoaW50KWFiaGkubGVuZ3RoKCksIGFiaGkpKTsKICAgIH0KICAgIGlmKGNpcC5sZW5ndGgoKSA+IDApCiAgICB7CiAgICAgICAgaW50IGxlbiA9IGNpcC5sZW5ndGgoKTsKICAgICAgICBpZihpczEoY3VyICsgMSwgY3VyICsgbGVuLCBjaXApKQogICAgICAgICAgICBhbnMgPSBtaW4oYW5zLCAxICsgc29sdmUoY3VyICsgbGVuLCBjaXApKTsKICAgIH0KICAgIHJldHVybiBkcFttcChjdXIsIGNpcCldID0gYW5zOwp9CmludCBtYWluKCkKewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBmcmVvcGVuKCJpbnAuaW4iLCAiciIsIHN0ZGluKTsKICAgIGZyZW9wZW4oIm91dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICBpbnQgdCwgdHQgPSAwOwogICAgY2luID4+IHQ7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgZHAuY2xlYXIoKTsKICAgICAgICB0dCsrOwogICAgICAgIGNpbiA+PiBzOwogICAgICAgIG4gPSBzLmxlbmd0aCgpOwogICAgICAgIHN0cmluZyBlbXAgPSAiIjsKICAgICAgICBjb3V0IDw8ICJDYXNlICMiIDw8IHR0IDw8ICI6ICIgPDwgc29sdmUoLTEsIGVtcCkgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==