#include <bits/stdc++.h>   using namespace std;   int kmp(string s) {     vector<int> lps(s.size(), 0);     for (int i = 1; i < s.size(); ++i) {       int index = lps[i - 1];       while (index > 0 && s[i] != s[index]) index = lps[index - 1];       if (s[i] == s[index])         lps[i] = index + 1;       else         lps[i] = index;     }     return lps[lps.size() - 1];   }   int func(string s) {     string t = s +  # ;     reverse(s.begin(), s.end());     t += s;     return kmp(t);   }   int main() {     int t;     cin >> t;     while (t--) {       string s;       cin >> s;       int l = 0, n = s.length();       for (int i = 0, j = n - 1; i < j; i++, j--) {         if (s[i] == s[j])           l++;         else           break;       }       string remaining = s.substr(l, n - 2 * l);       string ans = s.substr(0, l);       if (remaining.size()) {         int lp = func(remaining);         reverse(remaining.begin(), remaining.end());         int ls = func(remaining);         if (lp > ls) {           reverse(remaining.begin(), remaining.end());           ans += remaining.substr(0, lp);         } else           ans += remaining.substr(0, ls);       }       ans += s.substr(n - l, l);       cout << ans << endl;     }   }   