6894：CCPC Training Class

Baby volcano is helping his CCPC coach preparing a new CCPC training contest. He wants to generate high quality data on border tree(There is no need to know what border tree is), but he encounters some troubles. Could you please help him?

In this paragraph we formally define the data quality problem. For some string $s = s_1s_2s_3\cdots s_n$, we use $s[l:r]$ to denote the substring starts from $l$ and ends at $r$, if $l>r$, $s[l:r]$ is empty. We further define:
$$Lborder_i = \max\{0\leq j < i\ |\ s[1:j] = s[i-j+1:i]\}$$
to denote the longest border at some position $i$, then we define $D(i)$ to denote the length of border chain at position $i$:
$$D(i) = \begin{cases} 0 & i=0 \\ D(LBorder_i) + 1 & i > 0 \end{cases}$$
The quality $W$ of this string is define as the maximum of $D$:
$$W = \max_{i = 0}^{n} D(i)$$

To distinguish border tree with naive brute force algorithms, baby volcano need to generate strings such that its quality $W$ is as large as possible.

Now given a string $s$, you could permute $s$ arbitrarily. What is the maximum quality $W$ you could reach after permuting $s$?

In the first line there is a number $T$($T\leq 20$), denotes the number of test cases.
In the next $T$ lines, for each line there is a string $s$($1\leq |s|\leq 10^5$), denotes the input string, all inputs are formed in lowercases.

Output $T$ lines, for each line, you need to output ''Case #t: m''(without quotes), where t is the index of this test case, m is the maximum quality you could reach after permuting.