// #pragma GCC optimize("03,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <bitset>
#include <set>
#include <unordered_set>
#include <utility>
#include <numeric>
#include <iomanip>
#include <stack>
#include <list>
#include <bitset>
#include <sstream>
#include <random>
#include <stdlib.h>
#include <time.h>
#define ll long long
#define ld long double
#define INF 0x3f3f3f3f
#define MXN 2000005
#define cl(x) (x << 1)
#define cr(x) ((x << 1) | 1)
#define SZ(x) (int)x.size()
#define PB push_back
#define lowbit(x) (x & (-x))
#define NO_TAG false
#define P1 75577
#define P2 12721
#define MOD1 998244353
#define MOD2 1000000007

using namespace std;

// mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

// int rand_int(int lb, int ub) {
//     return uniform_int_distribution<int>(lb, ub)(gen);
// }

int n;
string s;
vector<pair<ll, ll>> HASH;
vector<pair<ll, ll>> p;

void build() {
    HASH.clear();
    HASH.resize(n + 1);
    pair<ll, ll> val = make_pair(0, 0);
    HASH[0] = val;
    for (int i = 0; i < n; i++) {
        val.first = (val.first * P1 + (int)s[i]) % MOD1;
        val.second = (val.second * P2 + (int)s[i]) % MOD2;
        HASH[i + 1] = val;
    }
    p.clear();
    p.resize(n + 1);
    val = make_pair(1, 1);
    p[0] = val;
    for (int i = 0; i < n; i++) {
        val.first = (val.first * P1) % MOD1;
        val.second = (val.second * P2) % MOD2;
        p[i + 1] = val;
    }
}

bool cmp(int i, int j, int len) {
    return ((HASH[i + len - 1].first - (HASH[i - 1].first * p[len].first) % MOD1 + MOD1) % MOD1 == (HASH[j + len - 1].first - (HASH[j - 1].first * p[len].first) % MOD1 + MOD1) % MOD1)
    && ((HASH[i + len - 1].second - (HASH[i - 1].second * p[len].second) % MOD2 + MOD2) % MOD2 == (HASH[j + len - 1].second - (HASH[j - 1].second * p[len].second) % MOD2 + MOD2) % MOD2);
}

void solve() {
    // 靠邀，我頭很痛。
    // 啊我微積分就退選，你覺得我看起來像會看懂題目的人嗎？
    cin >> s;
    n = s.size();
    build();
    int res = 0;
    string str = "";
    for (int len = 1; ; len++) {
        if (n / len < res) {
            break;
        }
        for (int i = 1; i + len <= n; i++) {
            for (int j = i + len; j + len - 1 <= n; j++) {
                if (cmp(i, j, len) && len > res) {
                    res = len;
                    str = s.substr(i - 1, len);
                }
            }
        }
    }
    cout << str << "\n";
    return ;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

*/