public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder out = new StringBuilder();
		int nCases = Integer.parseInt(in.readLine().trim());
		for (int nCase = 0; nCase < nCases; nCase++) {
			String word = in.readLine().trim();
			char[] p = new char[word.length()];
			char[] t = new char[word.length()];
			for (int i = 0; i < word.length(); i++) {
				char l = word.charAt(i);
				p[i] = l;
				t[word.length() - i - 1] = l;
			}
			preprocess(p);
			int len = KMP(p, t);
			if (len == 0)
				out.append(p[0] + "\n");
			else {
				for (int i = len - 1; i >= 0; i--)
					out.append(p[i]);
				out.append('\n');
			}
		}
		System.out.print(out);
	}