Matching Palindrome

메모리 제한1024 MB

요약

팰린드롬 P가 주어질 때, P 뒤에 붙여 팰린드롬이 되는 가장 짧은 비어 있지 않은 팰린드롬 Q를 구한다.

난이도: 보통10점 중 6점
유형: 문자열, 문자열 매칭, 그리디
정답자: 아직 제출이 없습니다

문제

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.

예제1

예제 1

입력

3
4
abba
4
cccc
6
cdccdc

예상 출력

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