#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
#define int long long
#define ll long long 
#define lll __int128_t
#define pb push_back
// #define double long double
#define pii pair<int,int>
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;
typedef pair<double, double> pdd;
vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}
void solve() {
    string s; cin >> s;
    int n = s.size();
    string ans;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            string temp = s.substr(i, j - i + 1);
            temp = temp + s;
            vector<int> z = z_function(temp);
            int len = temp.size();
            vector<int> calc;
            for(int k = j - i + 1; k < len; k++) {
                if(z[k] >= j - i + 1) {
                    calc.push_back(k);
                }
            }
            if(calc.size() > 1) {
                int l = calc[0] + j - i;
                int r = calc.back();
                if(l < r) {
                    if(ans.size() < j - i + 1) {
                        ans = s.substr(i, j - i + 1);
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}
signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t; cin >> t;
    while(t--) {
        solve();
    }
    
    return 0;
}