Bob 有一个字符串 $s_1s_2 \dots s_n$。他想找到该字符串中最长的平方子序列。你能帮帮他吗？

一个 $s_1s_2 \dots s_n$ 的子序列可以表示为字符串 $s_{p_1}s_{p_2} \dots s_{p_m}$，满足条件 $1 \le p_1 < p_2 < \dots < p_m \le n$。

字符串 $t_1t_2 \dots t_m$ 是一个平方串，当且仅当： $m$ 是偶数； $t_i = t_{i + \frac{m}{2}}$，对于 $i = 1, 2, \dots, \frac{m}{2}$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来描述所有测试用例。对于每个测试用例： 唯一的一行包含一个由 $n$ 个小写字母组成的字符串 $s_1s_2 \dots s_n$。

• $1 \le T, n \le 3000$
• 所有测试用例中 $n$ 的总和不超过 $3000$。

输出格式

对于每个测试用例，首先输出一行包含 “Case #x: m”（不含引号），其中 $x$ 是从 1 开始的测试用例编号，$m$ 是最长平方子序列的长度。 如果 $m$ 为正数，则在下一行输出一个字符串，表示该最长平方子序列。如果存在多个最优解，输出其中任意一个即可。

样例

样例输入 1

5
abba
abbab
abac
abcd
bbabab

样例输出 1

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

说明

对于最后一个样例测试用例，最长平方子序列也可以是 baba。