Problem: This is the hard 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 ≤ 10^5), 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 10^6.

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:
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {

	//static int p = 1000000007;
	static int p = 998244353;

	static void err() {
		System.out.println(-1);
	}
	
	static String lps1(String str) {
		
		str = str+"#"+new StringBuilder(str).reverse().toString();
		char s[] = str.toCharArray();
		int n=str.length(), pi[]=new int[n], j=0;
		for (int i = 1; i < n; i++) {
	         j = pi[i-1];
	        while (j > 0 && s[i] != s[j])
	            j = pi[j-1];
	        if (s[i] == s[j])
	            j++;
	        pi[i] = j;
	    }
		
		return str.substring(0,j);
		
	}
	
	
	static String lps(char[] arr) {
		boolean dp[][] = new boolean[arr.length][arr.length];
		for(int i=0; i<arr.length; i++) {
			dp[i][i]=true;
			if(i!=arr.length-1 && arr[i]==arr[i+1])
				dp[i][i+1]=true;
		}
		int diff=2;
		while(diff<arr.length) {
			for(int i=0; i<arr.length-diff; i++) {
				dp[i][i+diff] = dp[i+1][i+diff-1]&arr[i]==arr[i+diff]; 
			}
			diff++;
		}
		int index=0;
		for(int i=0; i<arr.length; i++) {
			if(dp[0][i])
				index=i;
		}
		return new String(Arrays.copyOfRange(arr, 0, index+1));
		
	}
	

	public static void main(String args[]) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);

		int t = 1;
		t = sc.nextInt();

		while (t-- > 0) {
			
			String ans = new String();

			char arr[] = sc.next().toCharArray();
			int i=0, j=arr.length-1;
			for(;j>i;j--,i++) {
				if(arr[i]!=arr[j])
					break;
			}
			if(i>=j)
				out.println(arr);
			else {
				ans+=new String(Arrays.copyOfRange(arr, 0, i));
				String str = new String(Arrays.copyOfRange(arr, i, j+1));
				String str1 = lps1(str);
				str = new StringBuilder(str).reverse().toString();
				String str2 = lps1(str);
				if(str1.length()>=str2.length())
					ans+=str1;
				else
					ans+=str2;
				ans+=new String(Arrays.copyOfRange(arr, j+1, arr.length));
				out.println(ans);
			}
		}
		out.flush();
	}
	
	
	
    
	static int count(int x, int[] arr) {
		int count = 0;

		for (int i = 0; i < arr.length; i++)
			if (arr[i] == x)
				count++;
		return count;
	}

	public static String reverseString(String str) {
		StringBuilder sb = new StringBuilder(str);
		sb.reverse();
		return sb.toString();
	}

	static boolean isPalindrome(String str) {
		int i = 0, j = str.length() - 1;

		while (i < j) {

			if (str.charAt(i) != str.charAt(j))
				return false;

			i++;
			j--;
		}
		return true;
	}

	static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

	public static int abs(int x) {
		return ((x > 0) ? x : -x);
	}

	public static long abs(long x) {
		return ((x > 0) ? x : -x);
	}

	public static int max(int a, int b) {
		return Math.max(a, b);
	}

	public static long max(long a, long b) {
		return Math.max(a, b);
	}

	public static int min(int a, int b) {
		return Math.min(a, b);
	}

	public static long min(long a, long b) {
		return Math.min(a, b);
	}

	static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static int modInverse(int a, int m) {
		int g = gcd(a, m);
		if (g != 1)
			return -1;
		else
			return power(a, m - 2, m);

	}

	// To compute x^y under modulo m
	static int power(int x, int y, int m) {
		if (y == 0)
			return 1;

		int p = power(x, y / 2, m) % m;
		p = (p * p) % m;

		if (y % 2 == 0)
			return p;
		else
			return (x * p) % m;
	}

	static int[] primeGenerator(int num) {
		int length = 0, arr[] = new int[num], a = num, factor = 1;
		if (num % 2 == 0) {
			while (num % 2 == 0) {
				num /= 2;
				factor *= 2;
			}
			arr[length++] = factor;
		}
		for (int i = 3; i * i <= a; i++) {
			factor = 1;
			if (num % i == 0) {
				while (num % i == 0) {
					num /= i;
					factor *= i;
				}
				arr[length++] = factor;
			}
		}
		if (num > 1)
			arr[length++] = num;
		return Arrays.copyOfRange(arr, 0, length);
	}

	static boolean isPrime(int n) {
		// Corner cases
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;

		// This is checked so that we can skip
		// middle five numbers in below loop
		if (n % 2 == 0 || n % 3 == 0)
			return false;

		for (int i = 5; i * i <= n; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;

		return true;
	}

	
	  static class Scanner { BufferedReader br; StringTokenizer st;
	  
	 Scanner() { br = new BufferedReader(new InputStreamReader(System.in)); }
	  
	  Scanner(String fileName) throws FileNotFoundException { br = new
	  BufferedReader(new FileReader(fileName)); }
	  
	  String next() throws IOException { while (st == null || !st.hasMoreTokens())
	  st = new StringTokenizer(br.readLine()); return st.nextToken(); }
	  
	  String nextLine() throws IOException { return br.readLine(); }
	  
	  int nextInt() throws IOException { return Integer.parseInt(next()); }
	  
	  long nextLong() throws NumberFormatException, IOException { return
	  Long.parseLong(next()); }
	  
	  double nextDouble() throws NumberFormatException, IOException { return
	  Double.parseDouble(next()); }
	  
	  boolean ready() throws IOException { return br.ready(); }
	  
	  }
	 

	static void sort(int[] a) {
		shuffle(a);
		Arrays.sort(a);
	}

	static void shuffle(int[] a) {
		int n = a.length;
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			int tmpIdx = rand.nextInt(n);
			int tmp = a[i];
			a[i] = a[tmpIdx];
			a[tmpIdx] = tmp;
		}
	}
}

class Pair {
	int x;
	int y;

	Pair(int a, int b) {
		x = a;
		y = b;
	}

	void print() {
		System.out.println(this.x + " " + this.y);
	}
}