## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

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

### Problem

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

### Input

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

### Output

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

### Limits

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

Solution Click Below:-  👉
👇👇👇👇👇

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

#### Test Set 1

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

#### Test Set 2

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

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.