#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};

const ll oo = 1e18;
const int N = 5e5 + 5, M = 1e4 + 5, MOD = 1e9 + 7;
#define EPS 1e-9

ll n, t, m, k, pw[N], h[N], p = 31;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //memset(dp, -1, sizeof dp);
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = (pw[i - 1] * p) % MOD;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        n = s.length();
        for (int i = 1; i <= n; i++) h[i] = (h[i - 1] + pw[i] * (s[i - 1] - 'A')) % MOD;
        string ans;
        for (int i = n; i >= 1; i--) {
            map<int, int> mp;
            int idx = 1e9;
            for (int j = i; j <= n; j++) {
                ll hash = (h[j] - h[j - i] + MOD) % MOD * pw[n - j] % MOD;
                if (mp[hash]) {
                    if (j - mp[hash] >= i) idx = min(idx, mp[hash]);
                } else mp[hash] = j;
            }
            if (idx != 1e9) {
                cout << s.substr(idx - i, i) << "\n";
                break;
            }
        }
    }
    return 0;
}