El genoma es una secuencia de cuatro ácidos nucleicos: A, T, C y G. Los elementos repetitivos dentro del genoma son patrones de ácidos nucleicos que aparecen en varias copias a lo largo del genoma sin solaparse. Por ejemplo, en un genoma simplificado $S = \mathtt{TATCGATCGAG}$ hay varios elementos repetitivos. En este caso, $R = \mathtt{ATCG}$ es el elemento repetitivo más largo, que aparece en $\mathtt{T}\underline{\mathtt{ATCG}}\mathtt{ATCGAG}$ y $\mathtt{TATCG}\underline{\mathtt{ATCG}}\mathtt{AG}$, en lugar de $\mathtt{ATCGA}$, cuyas dos posiciones de aparición se solapan. Tu tarea es identificar el elemento repetitivo más largo $R$ dentro de la secuencia del genoma dada $S$.

Entrada

La primera línea contiene un entero $T$, que representa el número de casos de prueba. Cada caso de prueba es una secuencia del genoma $S$.

Restricciones

• $1 \le T \le 50$.
• $S$ es una secuencia sobre el alfabeto $\Sigma = \{\mathtt{A}, \mathtt{T}, \mathtt{C}, \mathtt{G}\}$.
• $15 \le |S| \le 100$.
• Si hay varios elementos repetitivos de longitud máxima, imprime el que aparece primero (es decir, $\mathtt{CTT}$ en lugar de $\mathtt{ATG}$ en el quinto caso de prueba).

Salida

Para cada caso de prueba, imprime $R$, una cadena que corresponde al elemento repetitivo más largo del genoma dado $S$.

Ejemplos

Entrada 1

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

Salida 1

ATCG
GCGA
CATACG
GAT
CTT