#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef unordered_map<int,int> umap;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define popcount __builtin_popcount
#define case cout<<"Case "<<__testcase-testcase<<": ";
#define endl '\n'
#define inf 1e18

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 7;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcase=1;
    cin>>testcase;
    int __testcase=testcase;
    while(testcase--)
    {
        string s;
        cin>>s;
        int n=s.size();
        int Hash[n+1][n+1];
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                string t;
                for(int k=i;k<=j;k++) t+=s[k];
                Hash[i][j]=compute_hash(t);
            }
        }

        int ans[n+5][n+5];
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++) ans[i][j]=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                int len=j-i+1;
                for(int k=j+1;k<n;k++)
                {
                    if(k+len-1<n and Hash[k][k+len-1]==Hash[i][j]) ans[i][j]++,k=k+len-1;
                }
            }
        }

        int mx=0;
        pair<int,int> idx;
        for(int i=0;i<n;i++)
        for(int j=i;j<n;j++){
           if(ans[i][j]>0 and mx<j-i+1){
            mx=j-i+1;
            idx.fi=i;
            idx.se=j;
           }
        }
        string res;
        //cout<<mx<<' '<<idx.fi<<' '<<idx.se<<endl;
        for(int i=idx.fi;i<=idx.se;i++) res+=s[i];
        cout<<res<<endl;
    }
}