El Buscador Más Popular

Límite de tiempo: 2 segundos · Límite de memoria: 256 MB

Enunciado

Un buscador web guarda el registro de las últimas n consultas del día. Cada consulta es una palabra de letras minúsculas.

El equipo quiere saber cuál fue la palabra más buscada.

Si hay un empate (dos o más palabras con el mismo número máximo de apariciones) gana la que apareció primero en el registro.

Entrada

La primera línea contiene un entero T — el número de casos de prueba.

Cada caso consta de:

• Una línea con un entero n.
• Una línea con n palabras separadas por espacios.

Restricciones

• 1 <= T <= 100
• 1 <= n <= 2·10^5
• Cada palabra tiene entre 1 y 20 letras minúsculas (a–z), sin acentos ni espacios.
• La suma de n sobre todos los casos no excede 2·10^5.

Salida

Para cada caso, una línea con dos valores separados por un espacio: la palabra más buscada y su número de apariciones.

Ejemplo

Entrada

5
6
manzana platano manzana cereza platano manzana
4
perro gato gato perro
1
hola
5
ab abc ab abc abc
7
sol sol luna luna estrella luna sol

Salida

manzana 3
perro 2
hola 1
abc 3
sol 3

Explicación

Caso 1. manzana aparece 3 veces, platano 2 y cereza 1.

Caso 2. perro y gato aparecen 2 veces cada una. Empate: gana perro, que apareció primero en el registro (posición 1, contra la posición 2 de gato).

Caso 4. ab aparece 2 veces y abc 3. Que una palabra sea prefijo de otra no las hace iguales.

Caso 5. sol y luna aparecen 3 veces cada una. La primera aparición de sol está en la posición 1 y la de luna en la 3, así que gana sol.