일치하는 팰린드롬

영어 알파벳 소문자로만 이루어진 길이 $\mathbf{N}$의 팰린드롬 문자열 $\mathbf{P}$이 주어진다. $\mathbf{P}$에 $Q$를 이어 붙인 문자열이 팰린드롬이 되도록 하는 가장 짧은 비어 있지 않은 팰린드롬 문자열 $Q$를 구한다. 형식적으로, 문자열 $\mathbf{P}Q$가 팰린드롬을 이룬다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 문자열 $\mathbf{P}$는 영어 알파벳 소문자로만 이루어진 팰린드롬이다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 10^3$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{N} \le 10^5$.

입력의 첫째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 각 테스트 케이스의 첫째 줄에는 문자열 $\mathbf{P}$의 길이를 나타내는 정수 $\mathbf{N}$이 주어진다. 각 테스트 케이스의 둘째 줄에는 길이 $\mathbf{N}$의 팰린드롬 문자열 $\mathbf{P}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 위에서 설명한 비어 있지 않은 팰린드롬 문자열 $Q$이다.

케이스 1에서 가장 짧은 팰린드롬 문자열 $Q$는 abba이며, 이때 이어 붙인 문자열 $\mathbf{P}Q$은 팰린드롬인 abbaabba이 된다. 케이스 2에서 가장 짧은 팰린드롬 문자열 $Q$는 c이며, 이때 이어 붙인 문자열 $\mathbf{P}Q$은 팰린드롬인 ccccc이 된다. 케이스 3에서 가장 짧은 팰린드롬 문자열 $Q$는 cdc이며, 이때 이어 붙인 문자열 $\mathbf{P}Q$은 팰린드롬인 cdccdccdc이 된다.