#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

const int N = 110;

namespace Suffix_Array {
  // init: len = m, |char| = sigma, string = a[]
  int m, sigma, a[N], rnk[N], sa[N], h[N], cnt[N], p[N];
  
  void SA_sort() {
    rep (i, 1, sigma) cnt[i] = 0;
    rep (i, 1, m) cnt[rnk[i]] += 1;
    rep (i, 1, sigma) cnt[i] += cnt[i - 1];
    per (i, m, 1) sa[cnt[rnk[p[i]]]--] = p[i];
  }
  
  void Get_SA() {
    rep (i, 1, m) rnk[i] = a[i], p[i] = i;
    SA_sort();
    for (int len = 1, tot = 0; tot < m; sigma = tot, len <<= 1) {
      tot = 0;
      per (i, m, m - len + 1) p[++tot] = i;
      rep (i, 1, m) if (sa[i] > len) p[++tot] = sa[i] - len;
      SA_sort();
      rep (i, 1, m) p[i] = rnk[i];
      rnk[sa[1]] = tot = 1;
      rep (i, 2, m) {
        if (p[sa[i - 1]] == p[sa[i]] &&
          p[sa[i - 1] + len] == p[sa[i] + len]) rnk[sa[i]] = tot;
        else rnk[sa[i]] = ++tot;
      }
    }
    rep (i, 1, m) rnk[sa[i]] = i;
  }
  
  void Get_Height() {
    int k = 0;
    rep (i, 1, m) {
      if (rnk[i] == 1) continue;
      k = max(k - 1, 0);
      int j = sa[rnk[i] - 1];
      while (max(i, j) + k <= m && a[i + k] == a[j + k]) k++;
      h[rnk[i]] = k;
    }
  }
}

int n, st[N][20];
char s[N];

int lcp(int x, int y) {
  x = Suffix_Array::rnk[x];
  y = Suffix_Array::rnk[y];
  if (x > y) swap(x, y);
  int k = __lg(y - x);
  return min(st[x + 1][k], st[y - (1 << k) + 1][k]);
}

bool check(int l, int r) {
  int len = r - l + 1;
  rep (i, 1, l - len) {
    if (lcp(i, l) >= len) return 1;
  }
  rep (i, r + 1, n - len + 1) {
    if (lcp(i, l) >= len) return 1;
  }
  return 0;
}

void work() {
  cin >> (s + 1), n = strlen(s + 1);
  Suffix_Array::m = n, Suffix_Array::sigma = 26;
  rep (i, 1, n) Suffix_Array::a[i] = s[i] - 'A' + 1;
  Suffix_Array::Get_SA(), Suffix_Array::Get_Height();
  rep (i, 1, n) st[i][0] = Suffix_Array::h[i];
  rep (j, 1, 19) rep (i, 1, n - (1 << j) + 1)
    st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  int al = n + 1, ar = n + 1, cnt = 0;
  rep (l, 1, n) rep (r, l, n) if (check(l, r)) {
    if (r - l + 1 > cnt) cnt = r - l + 1, al = l, ar = r;
  }
  rep (i, al, ar) cout << s[i];
  cout << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}