#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 100010;

int len, ans;
string s;

bool check(int ln)
{
	for (int i = 0; i <= (int)s.size() - 2 * ln; i++)
	{
		//printf("i == %d\n", i);
		for (int j = i + ln; j <= s.size() - ln; j++)
		{
			if (s.substr(i, ln) == s.substr(j, ln))
			{
				//cout << s.substr(i, ln) << ' ' << s.substr(j, ln) << endl;
				if (ln > len)len = ln, ans = i;
				return true;
			}
		}
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		len = -1e9, ans = -1;
		cin >> s;

		int l = 1, r = (int)s.size() / 2;
		while (l < r)
		{
			int mid = (l + r + 1) >> 1;
			//cout << "mid " << mid << " l " << l << " r " << r << endl;
			if (check(mid))l = mid;
			else r = mid - 1;
		}

		//cout << "l " << len << " ans " << ans << endl;

		for (int i = ans; i < ans + len; i++)cout << s[i];
		cout << endl;
	}

	return 0;
}