#include <bits/stdc++.h>

#define el '\n'
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef long double ld;

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int P = 31, P2 = 37, M = 1e9 + 7, N = 1e5 + 5;

int pw[N], pw2[N], inv[N], inv2[N];

int add(int a, int b) {
    a = (a % M + M) % M;
    b = (b % M + M) % M;

    return (a + b) % M;
}

int mul(int a, int b) {
    a = (a % M + M) % M;
    b = (b % M + M) % M;

    return 1LL * a * b % M;
}

int modPow(int b, int p) {
    if (p == 0)
        return 1;

    int x = modPow(b, p / 2);

    return p % 2 == 0 ? mul(x, x) : mul(b, mul(x, x));
}

int modInvFer(int n) {
    return modPow(n, M - 2);
}

void pre() {
    pw[0] = inv[0] = pw2[0] = inv2[0] = 1;

    int invP = modInvFer(P), invP2 = modInvFer(P2);

    for (int i = 1; i < N; i++) {
        pw[i] = mul(pw[i - 1], P);
        inv[i] = mul(inv[i - 1], invP);

        pw2[i] = mul(pw2[i - 1], P2);
        inv2[i] = mul(inv2[i - 1], invP2);
    }
}

struct Hash {
    vector<pair<int, int>> prefixHash;

    Hash(string& sz) {
        prefixHash = vector<pair<int, int>> (sz.size());

        for (int i = 0; i < sz.size(); i++) {
            prefixHash[i].first = mul(sz[i] - 'a' + 1, pw[i]);
            prefixHash[i].second = mul(sz[i] - 'a' + 1, pw2[i]);

            if (i) {
                prefixHash[i].first = add(prefixHash[i].first, prefixHash[i - 1].first);
                prefixHash[i].second = add(prefixHash[i].second, prefixHash[i - 1].second);
            }
        }
    }

    pair<int, int> getHash(int l, int r) {
        return {
                mul(add(prefixHash[r].first, (l ? -prefixHash[l - 1].first : 0)), inv[l]),
                mul(add(prefixHash[r].second, (l ? -prefixHash[l - 1].second : 0)), inv2[l])
        };
    }
};

void testCase() {
    string s;
    cin >> s;

    int n = s.size();

    Hash hash(s);

    for (int len = n; len >= 1; len--) {
        for (int i = 0; i + len - 1 < n; i++) {
            for (int j = i + len; j + len - 1 < n; j++) {
                if (hash.getHash(i, i + len - 1) == hash.getHash(j, j + len - 1))
                    return cout << s.substr(i, len) << el, void();
            }
        }
    }
}

signed main() {
    Beevo

    pre();

    int t = 1;
    cin >> t;

    while (t--)
        testCase();
}