题目描述

给定一个长度为 $N$ 的回文字符串 $P$，仅由小写英文字母组成。找出最短的非空回文字符串 $Q$，使得 $P$ 与 $Q$ 拼接后形成回文串。形式化地说，字符串 $PQ$ 是一个回文串。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由 $2$ 行组成。每个测试用例的第一行包含一个整数 $N$，表示字符串 $P$ 的长度。每个测试用例的第二行包含一个长度为 $N$ 的回文字符串 $P$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是如上所述的非空回文字符串 $Q$。

3
4
abba
4
cccc
6
cdccdc

Case #1: abba
Case #2: c
Case #3: cdc

提示

在样例 $1$ 中，最短的回文字符串 $Q$ 是 abba，拼接后 $PQ$ 为 abbaabba，是一个回文串。

在样例 $2$ 中，最短的回文字符串 $Q$ 是 c，拼接后 $PQ$ 为 ccccc，是一个回文串。

在样例 $3$ 中，最短的回文字符串 $Q$ 是 cdc，拼接后 $PQ$ 为 cdccdccdc，是一个回文串。

限制条件

$1 \le T \le 100$。

字符串 $P$ 是回文串，仅由小写英文字母组成。

测试集 1

$1 \le N \le 10^3$。

测试集 2

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成