유전체는 네 가지 핵산 A, T, C, G로 이루어진 수열입니다. 유전체 안의 반복 요소는 유전체 전체에서 서로 겹치지 않는 여러 복사본으로 나타나는 핵산 패턴입니다. 예를 들어, 간단한 유전체 $S = \mathtt{TATCGATCGAG}$에는 몇 가지 반복 요소가 있습니다. 이때 $R = \mathtt{ATCG}$는 $\mathtt{T}\underline{\mathtt{ATCG}}\mathtt{ATCGAG}$와 $\mathtt{TATCG}\underline{\mathtt{ATCG}}\mathtt{AG}$에 나타나는 가장 긴 반복 요소입니다. 두 출현 위치가 겹치는 $\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$.
• 가장 긴 반복 요소가 여러 개라면 가장 먼저 나타나는 것을 출력하세요(즉, 다섯 번째 테스트 케이스에서는 $\mathtt{ATG}$가 아닌 $\mathtt{CTT}$).

출력

각 테스트 케이스에 대해 주어진 유전체 $S$의 가장 긴 반복 요소에 해당하는 문자열 $R$을 출력합니다.

예제

입력 1

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

출력 1

ATCG
GCGA
CATACG
GAT
CTT