Problem: This is the easy version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string s, consisting of lowercase English letters. Find the longest string, t, which satisfies the following conditions: 

  * The length of t does not exceed the length of s. 
  * t is a palindrome. 
  * There exists two strings a and b (possibly empty), such that t = a + b ( "+" represents concatenation), and a is prefix of s while b is suffix of s. 

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 1000), the number of test cases. The next t lines each describe a test case.

Each test case is a non-empty string s, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed 5000.

Output

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

Example

Input


5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba


Output


a
abcdfdcba
xyzyx
c
abba

Note

In the first test, the string s = "a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

  * Its length is 9, which does not exceed the length of the string s, which equals 11. 
  * It is a palindrome. 
  * "abcdfdcba" = "abcdfdc" + "ba", and "abcdfdc" is a prefix of s while "ba" is a suffix of s. 



It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" = "c" + "" and a or b can be empty. The other possible solution for this test is "s".

Solution (in JAVA):

Solution:
//Implemented By Aman Kotiyal Date:-25-Jan-2021  Time:-6:33:37 pm
import java.io.*;
import java.util.*;

public class ques4
{
	public static void main(String[] args)throws Exception{ new ques4().run();} 
	long mod=1000000000+7;
	
	void solve() throws Exception
	{
		for(int ii=ni();ii>0;ii--)
		{
			String s=ns();
			String front="";
			String back="";
			String mid="";
			int n=s.length();
			int st=0; int en=n-1;
			for(int i=0;i<s.length();i++) 
			{
				if(s.charAt(i)==s.charAt(n-i-1)  && i<n-i-1)
				{
					front+=s.charAt(i);
					back=s.charAt(n-i-1)+back;
				}
				else
				{
					st=i; en=n-i-1; break;
				}
			}
			s=s.substring(st,en+1);
			n=s.length();
			String rev="";
			for(int i=n-1;i>=0;i--)
				rev+=s.charAt(i);
			if(n>0) {
			StringHash h1=new StringHash(s);
			StringHash h2=new StringHash(rev);
			//forward----->
			int in1=0, in2=0,max=0,konsa=0;
			for(int i=0;i<n-1;i++)
			{
				if(h1.h[i]==h2.subhash(n-1-i-1, n-1))
				{
					int len=i+1;
					if(len>max)
					{
						max=len;
						in1=0;in2=i;
						konsa=1;
					}
				}
			}
			for(int i=0;i<n-1;i++)
			{
				if(h2.h[i]==h1.subhash(n-1-i-1, n-1))
				{
					int len=i+1;
					if(len>max)
					{
						max=len;
						in1=0;in2=i;
						konsa=2;
					}
				}
			}
			if(konsa==1)
				mid=s.substring(in1,in2+1);
			else
				mid=rev.substring(in1,in2+1);
			if(h1.h[n-1]==h2.h[n-1])
				mid=rev;
			}
			out.println(front+mid+back);
		}
	}
	
	// h[i] --> Gives Hash value till ith index(o based)
	// subhash(i,j) --> gives hash value from [i+1] to [j]
	class StringHash
	{
	   long h[];
	   long inv[];
	   StringHash(String s)
		{
			int l=s.length();
			inv=new long[l+1];
			h=new long[l];
			long p=31;long tpow=31;
			h[0]=(s.charAt(0)-'a'+1)%mod;
			for(int i=1;i<l;i++)
			{
				char c=s.charAt(i);
				h[i]=(h[i-1] + (c-'a'+1)*tpow)%mod;
				tpow=(tpow*p)%mod;
			}
			inv[0]=1; inv[1]=expo(31,mod-2);
			   for (int i = 2; i <inv.length; i++) 
				   inv[i]=(inv[i-1]*inv[1])%mod;
		 }
	   long subhash(int l,int r)
		{
			return (  ((h[r]-h[l]+mod)%mod)  * inv[l+1]  )%mod;
		}
	}
	
	/*FAST INPUT OUTPUT & METHODS BELOW*/
	
	private byte[] buf=new byte[1024];
	private int index;
	private InputStream in;
	private int total;
	private SpaceCharFilter filter;
	PrintWriter out;
	
	int min(int... ar){int min=Integer.MAX_VALUE;for(int i:ar)min=Math.min(min, i);return min;}
	long min(long... ar){long min=Long.MAX_VALUE;for(long i:ar)min=Math.min(min, i);return min;}
	int max(int... ar) {int max=Integer.MIN_VALUE;for(int i:ar)max=Math.max(max, i);return max;}
	long max(long... ar) {long max=Long.MIN_VALUE;for(long i:ar)max=Math.max(max, i);return max;}
	
	void shuffle(int a[]) {
		ArrayList<Integer> al = new ArrayList<>();
		for(int i=0;i<a.length;i++) 
			al.add(a[i]);
		
		Collections.sort(al);
		for(int i=0;i<a.length;i++) 
			a[i]=al.get(i);
	}
	long lcm(long a,long b)
	{
		return (a*b)/(gcd(a,b));
	}
	
	int gcd(int a, int b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b%a, a); 
	} 
	long gcd(long a, long b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b%a, a); 
	}
	/* for (1/a)%mod = ( a^(mod-2) )%mod  ----> use expo to calc -->(a^(mod-2)) */
	long expo(long p,long q)  /*  (p^q)%mod   */
	{
		long z = 1;
		while (q>0) {
			if (q%2 == 1) {
				z = (z * p)%mod;
			}
			p = (p*p)%mod;
			q >>= 1;
		}
		return z;
	}
	void run()throws Exception
	{
		in=System.in; out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	private int scan()throws IOException
	{
		if(total<0)
			throw new InputMismatchException();
		if(index>=total)
		{
			index=0;
			total=in.read(buf);
			if(total<=0)
				return -1;
		}
		return buf[index++];
	}
	private int ni() throws IOException 
	{
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = scan();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = scan();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private long nl() throws IOException 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = scan()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = scan();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = scan();
		}
	}
	private double nd() throws IOException{
		return Double.parseDouble(ns());
	}
	private String ns() throws IOException {
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		StringBuilder res = new StringBuilder();
		do {
			if (Character.isValidCodePoint(c))
				res.appendCodePoint(c);
			c = scan();
		} while (!isSpaceChar(c));
		return res.toString();
	}
	private String nss() throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		return br.readLine();
	}
	private char nc() throws IOException 
	{
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		return (char) c;
	}
	private boolean isWhiteSpace(int n)
	{
		if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
			return true;
		return false;
	}
	private boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhiteSpace(c);
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}