#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pii pair<int, int> 
#define fi first
#define se second
using namespace std;
// map<string, char> mp;
const int mod1 = 998244353;
const int mod2 = 1e7 + 49;
const int base1 = 250316;
const int base2 = 171925;
struct hash {
    int n; string s;
    vector<pii> ha, pw;
    void init(string t) {
        s = t, n = s.size();
        ha.resize(n + 1), pw.resize(n + 1);
        pw[0] = {1, 1};
        F(i, 1, n) {
            pw[i].fi = 1ll * pw[i - 1].fi * base1 % mod1;
            pw[i].se = 1ll * pw[i - 1].se * base2 % mod2;
        }
        F(i, 1, n) {
            ha[i].fi = (1ll * ha[i - 1].fi * base1 + s[i - 1]) % mod1;
            ha[i].se = (1ll * ha[i - 1].se * base2 + s[i - 1]) % mod2;
        }
    }
    pii hsh(int l, int r) {
        int x = (ha[r].fi - (1ll * ha[l - 1].fi * pw[r - l + 1].fi) % mod1 + mod1) % mod1;
        int y = (ha[r].se - (1ll * ha[l - 1].se * pw[r - l + 1].se) % mod2 + mod2) % mod2;
        return {x, y};
    }
} a;
string s;
int n;
void sol() {
    cin >> s;
    n = s.size();
    a.init(s);
    Fd(k, n / 2, 1) {
        F(i, 1, n) {
            F(j, i + k, n) {
                if(j + k - 1 > n || i + k - 1 > n) continue;
                if(a.hsh(i, i + k - 1) == a.hsh(j, j + k - 1)) {
                    // cout << k << "\n";
                    F(z, i, i + k - 1) cout << s[z - 1];
                    cout << "\n";  
                    return;
                }
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while(t --) sol();
}