[Solution] Matching Palindrome Round E Solution 2022 - Kick Start 2022

Problem

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

Input

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

Output

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

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

String P$P$ is a palindrome consisting of only lowercase letters of the English alphabet.

Test Set 1

Time limit: 20 seconds.
1≤N≤103$1\le \mathbf{N}\le {10}^3$.

Test Set 2

Time limit: 40 seconds.
1≤N≤105$1\le \mathbf{N}\le {10}^5$.

In Case 1, the shortest palindrome string Q$Q$ is abba such that the concatenation PQ$\mathbf{P}Q$ is abbaabba which is a palindrome.
In Case 2, the shortest palindrome string Q$Q$ is c such that the concatenation PQ$\mathbf{P}Q$ is ccccc which is a palindrome.
In Case 3, the shortest palindrome string Q$Q$ is cdc such that the concatenation PQ$\mathbf{P}Q$ is cdccdccdc which is a palindrome.