시간 제한메모리 제한제출정답맞힌 사람정답 비율
서브태스크 참고 (추가 시간 없음) 1024 MB766100.000%

문제

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

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of two lines. The first line of each test case contains an integer $\mathbf{N}$ denoting the length of the string $\mathbf{P}$. The second line of each test case contains a palindrome string $\mathbf{P}$ of length $\mathbf{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.

제한

  • $1 \le \mathbf{T} \le 100$.
  • String $\mathbf{P}$ is a palindrome consisting of only lowercase letters of the English alphabet.

Test Set 1 (10점)

시간 제한: 20 초

  • $1 \le \mathbf{N} \le 10^3$.

Test Set 2 (18점)

시간 제한: 40 초

  • $1 \le \mathbf{N} \le 10^5$.

예제 입력 1

3
4
abba
4
cccc
6
cdccdc

예제 출력 1

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

In Case 1, the shortest palindrome string $Q$ is abba such that the concatenation $\mathbf{P}Q$ is abbaabba which is a palindrome.

In Case 2, the shortest palindrome string $Q$ is c such that the concatenation $\mathbf{P}Q$ is ccccc which is a palindrome.

In Case 3, the shortest palindrome string $Q$ is cdc such that the concatenation $\mathbf{P}Q$ is cdccdccdc which is a palindrome.

채점 및 기타 정보

  • 예제는 채점하지 않는다.