Link đề (Google)

Bạn được cung cấp một chuỗi palindrome \(P\) có độ dài \(N\) chỉ gồm các chữ cái viết thường của bảng chữ cái tiếng Anh. Tìm chuỗi palindrome không rỗng ngắn nhất \(Q\) sao cho \(P\) nối với \(Q\) tạo thành palindrome.

Input

Dòng đầu tiên của đầu vào cho biết số lượng các trường hợp thử nghiệm, các trường hợp thử nghiệm \(T\). \(T\) theo sau. Mỗi trường hợp kiểm thử bao gồm hai dòng. Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa một số nguyên \(N\) biểu thị độ dài của chuỗi \(P\). Dòng thứ hai của mỗi trường hợp kiểm tra chứa một chuỗi palindrome \(P\) có độ dài \(N\).

Output

Đối với mỗi trường hợp thử nghiệm, in ra một dòng có dạng Case #x: y, trong đó \(x\) là số trường hợp thử nghiệm (bắt đầu từ \(1\)) và \(y\) là chuỗi palindrome không rỗng \(Q\) như mô tả ở trên.

Example

3
4
abba
4
cccc
6
cdccdc

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