P16887 [GKS 2022 #E] Matching Palindrome

You are given a palindrome string $P$ of length $N$ consisting of only lowercase letters of the English alphabet. Find the shortest non-empty palindrome string $Q$ such that $P$ concatenated with $Q$ forms a palindrome. Formally, the string $PQ$ forms a palindrome.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of $2$ lines. The first line of each test case contains an integer $N$ denoting the length of the string $P$. The second line of each test case contains a palindrome string $P$ of length $N$.

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number starting from $1$ and $y$ is the non-empty palindrome string $Q$ as described above.

In Case $1$, the shortest palindrome string $Q$ is `abba` such that the concatenation $PQ$ is `abbaabba`, which is a palindrome. In Case $2$, the shortest palindrome string $Q$ is `c` such that the concatenation $PQ$ is `ccccc`, which is a palindrome. In Case $3$, the shortest palindrome string $Q$ is `cdc` such that the concatenation $PQ$ is `cdccdccdc`, which is a palindrome. ### Limits $1 \le T \le 100$. String $P$ is a palindrome consisting of only lowercase letters of the English alphabet. **Test Set 1** $1 \le N \le 10^3$. **Test Set 2** $1 \le N \le 10^5$.