func_code_string: #include <bits/stdc++.h>   using namespace std;   vector<long long> z;   const long long N = 5e3 + 7, M1 = 1e9 + 7, M2 = 1e9 + 9, b1 = 127, b2 = 239;   long long maxi1[N], maxi2[N], maxx[N];   pair<long long, long long> h1[N], h2[N];   pair<long long, long long> poww[N];   string best;   long long mod(long long x, long long m) {     x %= m;     if (x < 0) x += m;     return x;   }   pair<long long, long long> get_h(long long l, long long r) {     long long res1 =         mod(h1[r].first - h1[l - 1].first * poww[r - l + 1].first, M1);     long long res2 =         mod(h1[r].second - h1[l - 1].second * poww[r - l + 1].second, M2);     return {res1, res2};   }   pair<long long, long long> get_h2(long long l, long long r) {     long long res1 =         mod(h2[r].first - h2[l - 1].first * poww[r - l + 1].first, M1);     long long res2 =         mod(h2[r].second - h2[l - 1].second * poww[r - l + 1].second, M2);     return {res1, res2};   }   void solve(string s) {     long long n = s.length();     string t = s;     long long ser = (n + 1) / 2;     long long len = 0;     while (len != n && s[len] == s[n - len - 1]) {       len++;     }     if (len == n) {       best = s;       return;     }     if (2 * len > (long long)best.size()) {       best =   ;       for (long long i = 0; i < len; i++) best += s[i];       for (long long i = len - 1; i >= 0; i--) best += s[i];     }     for (long long i = 0; i < ser; i++) {       maxi1[i] = -1;       long long l = i, r = i;       while (l >= 0 && r < n && s[l] == s[r]) {         l--;         r++;         maxi1[i] += 2;         if (l < len) {           long long curlen = maxi1[i] + 2 * (l + 1);           if (curlen > (long long)best.size()) {             best =   ;             for (long long j = 0; j < r; j++) {               best += s[j];             }             for (long long j = l; j >= 0; j--) {               best += s[j];             }           }         }       }     }     if (n % 2 == 1) ser--;     for (long long i = 0; i < ser; i++) {       maxi2[i] = 0;       long long l = i, r = i + 1;       while (l >= 0 && r < n && s[l] == s[r]) {         l--;         r++;         maxi2[i] += 2;         if (l < len) {           long long curlen = maxi2[i] + 2 * (l + 1);           if (curlen > (long long)best.size()) {             best =   ;             for (long long j = 0; j < r; j++) {               best += s[j];             }             for (long long j = l; j >= 0; j--) {               best += s[j];             }           }         }       }     }   }   signed main() {     ios_base ::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     long long t;     cin >> t;     for (long long i = 0; i < t; i++) {       string s;       cin >> s;       best = s[0];       solve(s);       reverse(s.begin(), s.end());       solve(s);       cout << best << endl;     }     return 0;   }   