#include<bits/stdc++.h>
#define N 300005
using namespace std;


vector<int> KMP(string s){
    int sz = s.size();
    vector<int> pi(sz);
    for(int i = 1; i < sz; i++){
        int len = pi[i-1];
        while(len != 0 && s[i] != s[len]) len = pi[len-1];
        if(s[i] == s[len]) pi[i] = len+1;
    }
    return pi;
}

signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int t; cin >> t;
    while(t--){
        string str; cin >> str;
        int sz = str.size();
        int mx = 0, ans = 0;
        for(int i = 1; i < sz; i++){
            string test = str.substr(i) + '@' + str.substr(0, i);
            int pre = i;
            int where = sz - i;
            // cout << test << '\n';
            vector<int> pi = KMP(test);
            for(int j = where+1; j < pi.size(); j++){
                if(pi[j] > mx || (pi[j] == mx && j-where-mx < ans)){
                    mx = pi[j];
                    ans = j - where - mx;
                }
                // cout << pi[i] << " ";
            }
            // cout << mx << '\n';
        }
        for(int i = ans; i < ans+mx; i++) cout << str[i];
        cout << '\n';
    }

    return 0;
}