409641: GYM103652 F Square Subsequences

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 < p_2 < \ldots < 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}$$$.

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$$$.

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.

5
abba
abbab
abac
abcd
bbabab

Case #1: 2
aa
Case #2: 4
abab
Case #3: 2
aa
Case #4: 0
Case #5: 4
bbbb

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