Programacion Competitiva Bolivia

La Subcadena comun mas larga

Una subcadena son consecutivas partes de una cadena (Por ejemplo ab es subcadena de abcd). Un problema muy usual resuelto con programacion dinamica es encontrar la cadena (o cadenas) mas larga que es sub cadena entre dos cadenas y son comunes. Por ejemplo:
aaabbb
bbaabb
La cadena que es subcadena de ambas cadenas y a la vez es mas larga es aabb (longitud 4)

Tu tarea es encontrar la longitud de la subcadena común mas larga entre K cadenas

Input

La primera linea contiene un entero T, el numero de casos de prueba (1 ≤ T ≤ 20).

Cada caso de prueba consiste de una linea de entero K (1 ≤ K ≤ 10), y K líneas a continuación que contiene una cadena S (1 ≤ length(S) ≤ 10^4), las cadenas solo contienen caracteres alfabeticos de a hasta z

Output

La salida esta compuesta de T lineas, para cada caso de prueba imprimir la longitud de la subcadena mas larga que sea comun entre las K cadenas.

Example

Input:
2
2
aaabbb
bbaabb
3
icode
coder
contest


Output:
4
2