#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;
const unsigned BASE = 1000000007;
char S[MAXN];
unsigned L[MAXN], P[MAXN];

void __gen_pow() {
    P[0] = 1;
    for(int i = 1; i < MAXN; i++) {
        P[i] = P[i - 1] * BASE;
    }
}

void __gen_hash(int n) {
    L[0] = S[0];
    for(int i = 1; i < n; i++) {
        L[i] = L[i - 1] * BASE + S[i];
    }
}

unsigned __rev_hash(int j) {
    unsigned val = 0;
    for(int i = j; i > -1; i--) {
        val = val * BASE + S[i];
    }
}

bool check(int j, int n) {
    unsigned hash_val = __rev_hash(j), val_now;
    int lim = n - j;
    for(int i = 0; i < lim; i++) {
        val_now = L[i + j];
        if(i > 0) {
            val_now = val_now - L[i - 1] * P[j + 1];
        }
        if(val_now == hash_val) {
            return true;
        }
    }
    return false;
}

int main() {
    __gen_pow();
    int T;
    scanf("%d\n", &T);
    while(T--) {
        gets(S);
        int n = strlen(S);
        __gen_hash(n);
        int l = n - 1, r = n - 1, ans = 0;
        set<int> st;
        st.insert(l);
        while(1) {
            if(check(l, n)) {
                ans = max(ans, l);
                l = (l + r) / 2;
            } else {
                l /= 2;
            }
            if(st.count(l) > 0) break;
            st.insert(l);
        }
        for(int i = ans; i > -1; i--) {
            putchar(S[i]);
        }
        puts("");
    }
    return 0;
}