#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define mp make_pair
#define eb emplace_back
#define pb push_back
typedef pair<int,int> pii;

int mod=1e15+7;
int base=31;
string s;
int idx;

bool check(int x){
    int h=0,xx=1;
    bool res=0;idx=1e9;
    map<int,int> mp;
    for(int i=0;i<x;i++){
        h+=(s[i]-'A'+1);
        h*=base;h%=mod;
        xx*=base;xx%=mod;
    }
    mp[h]=x-1;
    for(int i=x;i<s.length();i++){
        h-=((s[i-x]-'A'+1ll)*xx)%mod;
        h+=mod;
        h+=(s[i]-'A'+1);
        h*=base;h%=mod;

        if(mp.find(h)==mp.end())mp[h]=i;
        else{
            if(i-mp[h]>=x){
                idx=min(idx,mp[h]);
                res=1;
            }
        }
    }
    return res;
}

void solve(){
    cin>>s;
    int lo,hi,mid;
    lo=1;hi=s.length();
    while(lo<hi){
        mid=hi-(hi-lo)/2;
        if(check(mid)){
            lo=mid;
        }else{
            hi=mid-1;
        }
    }
    check(lo);
    for(int i=idx-lo+1;i<=idx;i++){
        cout<<s[i];
    }
    cout<<'\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int tc;
    cin>>tc;
    while(tc--){
        solve();
    }
}