基因是由四种核酸 A、T、C 和 G 组成的序列。基因组内的重复元素是指在基因组中多次出现且互不重叠的核酸模式。例如，给定一个玩具基因组 $S = \text{TATCGATCGAG}$，其中存在一些重复元素，例如 $R = \text{ATCG}$ 是出现在 $\text{TATCGATCGAG}$ 中的最长重复元素，而不是 $\text{ATCGA}$，因为 $\text{ATCGA}$ 的两个出现位置发生了重叠。你的任务是找出给定基因组序列 $S$ 中的最长重复元素 $R$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例为一个基因组序列 $S$。

数据范围

• $1 \le T \le 50$。
• $S$ 是由字母表 $\Sigma = \{\text{A, T, C, G}\}$ 组成的序列。
• $15 \le |S| \le 100$。
• 如果存在多个最长重复元素，请输出最先出现的那一个（例如，在第五个测试用例中输出 $\text{CTT}$ 而不是 $\text{ATG}$）。

输出格式

对于每个测试用例，输出 $R$，即给定基因组 $S$ 中对应的最长重复元素。

样例

输入 1

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

输出 1

ATCG
GCGA
CATACG
GAT
CTT