Longest Palindromic Substring

You are given a string (S) and your task is to find the longest palindromic substring in (S). A palindromic string is defined as a string that reads the same forward and backward. For example, if (S = \texttt{racecar}), the longest palindromic substring is (\texttt{racecar}). The problem requires you to solve multiple test cases efficiently (an (O(n^2)) approach is acceptable).

inputFormat

The input begins with an integer (T) denoting the number of test cases. For each test case, the first line contains an integer (N) (the length of the string), followed by a line containing the string (S). Note that the integer (N) is provided for convenience; you may derive the string length from (S) itself.

outputFormat

For each test case, output the longest palindromic substring in a new line.## sample

2
7
racecar
6
banana

racecar
anana