#include <bits/stdc++.h>   using namespace std;   inline void Boost() {     ios::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);   }   const int NMax = 1e6 + 50;   string convert(const string &s) {     string ret =  @ ;     for (int i = 0; i < (int)s.size(); ++i) {       ret +=  #  + s.substr(i, 1);     }     ret +=  #$ ;     return ret;   }   int P[NMax * 2];   void Solve() {     string s;     cin >> s;     int n = (int)s.size();     int a = 0;     int b = n - 1;     while (a <= b) {       if (a == b) {         cout << s <<   n ;         return;       }       if (s[a] == s[b]) {         ++a;         --b;         if (a > b) {           cout << s <<   n ;           return;         }       } else {         string nw = convert(s);         int cen = 0, r = 0;         for (int i = 0; i < (int)nw.size(); ++i) P[i] = 0;         for (int i = 1; i < (int)nw.size() - 1; ++i) {           int mir = cen - (i - cen);           if (r > i) {             P[i] = min(r - i, P[mir]);           }           while (nw[i + 1 + P[i]] == nw[i - 1 - P[i]]) {             P[i]++;           }           if (i + P[i] > r) {             cen = i;             r = i + P[i];           }         }         int best = 0;         int pos = 0;         for (int i = 1; i < (int)nw.size() - 1; i++) {           int start = (i - 1 - P[i]) / 2;           int fin = start + P[i] - 1;           if (start < a) {             int mv = a - start;             start += mv;             fin -= mv;           }           if (fin > b) {             int mv = fin - b;             start += mv;             fin -= mv;           }           if (start != a && fin != b) continue;           if (start <= fin && (fin - start + 1) > best) {             best = fin - start + 1;             pos = start;           }         }         for (int i = 0; i < a; ++i) cout << s[i];         for (int i = pos; i < pos + best; ++i) cout << s[i];         for (int i = a - 1; i >= 0; --i) cout << s[i];         cout <<   n ;         return;       }     }   }   int main() {     Boost();     int t;     cin >> t;     while (t--) {       Solve();     }     return 0;   }   