Genom jest ciągiem złożonym z czterech kwasów nukleinowych: A, T, C i G. Powtarzające się elementy w genomie to wzorce kwasów nukleinowych występujące w wielu kopiach w całym genomie, które się nie nakładają. Na przykład w uproszczonym genomie $S = \mathtt{TATCGATCGAG}$ występuje kilka powtarzających się elementów. Najdłuższym z nich jest $R = \mathtt{ATCG}$, występujący w $\mathtt{T}\underline{\mathtt{ATCG}}\mathtt{ATCGAG}$ i $\mathtt{TATCG}\underline{\mathtt{ATCG}}\mathtt{AG}$, a nie $\mathtt{ATCGA}$, którego dwa wystąpienia nakładają się na siebie. Twoim zadaniem jest znalezienie najdłuższego powtarzającego się elementu $R$ w danym ciągu genomu $S$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$, oznaczającą liczbę przypadków testowych. Każdy przypadek testowy jest ciągiem genomu $S$.

Ograniczenia

• $1 \le T \le 50$.
• $S$ jest ciągiem nad alfabetem $\Sigma = \{\mathtt{A}, \mathtt{T}, \mathtt{C}, \mathtt{G}\}$.
• $15 \le |S| \le 100$.
• Jeśli istnieje wiele najdłuższych powtarzających się elementów, wypisz ten, który występuje jako pierwszy (czyli $\mathtt{CTT}$ zamiast $\mathtt{ATG}$ w piątym przypadku testowym).

Wyjście

Dla każdego przypadku testowego wypisz $R$, czyli napis odpowiadający najdłuższemu powtarzającemu się elementowi w danym genomie $S$.

Przykład

Wejście 1

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

Wyjście 1

ATCG
GCGA
CATACG
GAT
CTT