#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MXN=1000;
//double hash
const int P1=12421;
const int P2=75577;
const int MOD=1e9+7;
pair<int,int> Hash[MXN];
void build(const string& s){
  pair<int,int> val = make_pair(0,0);
  for(int i=0; i<s.size(); i++){
  val.first = (val.first * P1 + s[i]) % MOD;
  val.second = (val.second * P2 + s[i]) % MOD;
  Hash[i] = val;
  }
}

int qpow( int n, int k ) {
    int res=1;
    for( ; k ; n=n*n%MOD, k>>=1 ) if( k&1 ) res=res*n%MOD;
    return res;
}

bool cmp( int i, int j, int len ) {
    return ((Hash[i+len].first-Hash[i].first*qpow(P1,len)%MOD+MOD)%MOD == (Hash[j+len].first-Hash[j].first*qpow(P1,len)%MOD+MOD)%MOD)
    && ((Hash[i+len].second-Hash[i].second*qpow(P2,len)%MOD+MOD)%MOD == (Hash[j+len].second-Hash[j].second*qpow(P2,len)%MOD+MOD)%MOD);
}

signed main()
{
    // H[r] - H[l-1] * p^(r-l+1)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q;
    cin>>q;
    for(;q--;) {
        string str, res;
        cin>>str;
        int n=str.size(), maxi=0;
        build(str);
        for( int k=1 ; k <= n ; k++ ) {
            for( int i=0 ; i+k <= n ; i++ ) {
                for( int j=i+k ; j+k <= n ; j++ ) {
                    if( cmp(i,j,k) && k > maxi ) 
                        maxi=k, res=str.substr(i+1,k);
                }
            }
        }
        cout<<res<<'\n';
    }
}