ゲノムは、4 種類の核酸 A、T、C、G からなる列です。ゲノム内の反復要素とは、ゲノム全体で互いに重ならない複数のコピーとして現れる核酸のパターンです。例えば、簡単なゲノム $S = \mathtt{TATCGATCGAG}$ にはいくつかの反復要素があります。このとき、$R = \mathtt{ATCG}$ は $\mathtt{T}\underline{\mathtt{ATCG}}\mathtt{ATCGAG}$ と $\mathtt{TATCG}\underline{\mathtt{ATCG}}\mathtt{AG}$ に現れる最長の反復要素です。2 つの出現位置が重なる $\mathtt{ATCGA}$ ではありません。あなたの課題は、与えられたゲノム列 $S$ の中で最長の反復要素 $R$ を見つけることです。

入力

最初の行には、テストケースの数を表す整数 $T$ が与えられます。各テストケースはゲノム列 $S$ です。

制約

• $1 \le T \le 50$。
• $S$ はアルファベット $\Sigma = \{\mathtt{A}, \mathtt{T}, \mathtt{C}, \mathtt{G}\}$ からなる列です。
• $15 \le |S| \le 100$。
• 最長の反復要素が複数ある場合は、最初に現れるものを出力してください（つまり、5 番目のテストケースでは $\mathtt{ATG}$ ではなく $\mathtt{CTT}$）。

出力

各テストケースについて、与えられたゲノム $S$ の最長の反復要素に対応する文字列 $R$ を出力します。

入出力例

入力 1

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

出力 1

ATCG
GCGA
CATACG
GAT
CTT