Rohan wants to impress his girlfriend by sharing a coding question which is going to be asked in the test. And Rohan is from mechanical department so he has no idea about the problem. He only managed to copy down the question as it is. The problem statement is as follows: You are given a string S, your task is to find the longest palindromic substring in S. Incase of conflict ,return the substring which occurs first( with least starting index). Help Rohan to solve the question.

Input Format: First line contains number of test cases n Then subsequent n lines contains string S

Output: For each string S, print the longest palindromic substring.

Constraint: 1 ≤ |S| ≤ 10^3