#include <bits/stdc++.h>   using namespace std;   int t[2000002];   int longestPrefix(string &s) {     t[0] = 0;     for (int pos = 1; pos < s.length(); ++pos) {       int prev = t[pos - 1];       while (prev > 0 && s[pos] != s[prev]) {         prev = t[prev - 1];       }       if (s[pos] == s[prev]) {         t[pos] = prev + 1;       } else {         t[pos] = prev;       }     }     return t[s.length() - 1];   }   int main() {     int t;     cin >> t;     while (t-- > 0) {       string s;       cin >> s;       int lindex = 0, rindex = s.length();       while (lindex < rindex && s[lindex] == s[rindex - 1]) {         ++lindex;         --rindex;       }       if (lindex >= rindex) {         cout << s << endl;         continue;       }       string mid = s.substr(lindex, rindex - lindex);       string rmid = mid;       reverse(rmid.begin(), rmid.end());       string pre = mid +  *  + rmid;       string suf = rmid +  *  + mid;       int pref = longestPrefix(pre);       int suff = longestPrefix(suf);       int len = max(pref, suff);       for (int i = 0; i < lindex; ++i) {         cout << s[i];       }       if (pref >= suff) {         for (int i = lindex; i < lindex + pref; ++i) {           cout << s[i];         }       } else {         for (int i = rindex - suff; i < rindex; ++i) {           cout << s[i];         }       }       for (int i = rindex; i < s.length(); ++i) {         cout << s[i];       }       cout << endl;     }     return 0;   }   