You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.
A substring is a contiguous segment of a string.
For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first and only one of each test case contains a string 'STR'.
Output Format :
For every test case, print the longest palindromic substring.
If there are multiple possible answers then you need to print the substring which has the lowest starting index.
Do not print anything. It has already been taken care of. Just implement the given function.
Try to solve it using O(1) space complexity.
1 <= T <= 5
0 <= N <= 100
Time Limit: 1 sec