F. Square Subsequences
time limit per test
2 s
memory limit per test
256 mebibytes
input
standard input
output
standard output

Bob has a string $$$s_{1} s_{2} \cdots s_{n}$$$. He would like to find its longest subsequence that is a square. Could you please help him?

A subsequence of $$$s_{1} s_{2} \cdots s_{n}$$$ can be represented as a string $$$s_{p_1} s_{p_2} \cdots s_{p_m}$$$ meeting the condition that $$$1 \leq p_1 \lt p_2 \lt \ldots \lt p_m \leq n$$$.

A string $$$t_{1} t_{2} \cdots t_{m}$$$ is a square if and only if:

  • $$$m$$$ is even;
  • $$$t_i = t_{i + \frac{m}{2}}$$$ for $$$i = 1, 2, \ldots, \frac{m}{2}$$$.
Input

The input contains several test cases. The first line contains an integer $$$T$$$ indicating the number of test cases. The following describes all test cases. For each test case:

The only line contains a string of $$$n$$$ lowercase letters, $$$s_{1} s_{2} \cdots s_{n}$$$.

  • $$$1 \leq T, n \leq 3000$$$
  • The sum of $$$n$$$ in all test cases does not exceed $$$3000$$$.
Output

For each test case, firstly output a line containing "Case #x: m" (without quotes), where x is the test case number starting from $$$1$$$, and m is the length of the longest square subsequence.

If m is positive, then output a string in the next line, representing the longest square subsequence. If there are many optimal solutions, please output any of them.

Example
Input
5
abba
abbab
abac
abcd
bbabab
Output
Case #1: 2
aa
Case #2: 4
abab
Case #3: 2
aa
Case #4: 0
Case #5: 4
bbbb
Note

For the last sample test case, the longest square subsequence can be baba as well.