Descripción
En el planeta OBI (planeta de los Ositos Barrigones Intergalácticos), el juego de moda entre los jóvenes es el Crash Loyale, un juego sobre combates con cartas.
Como en todo juego de cartas, las mejores cartas son las que tienen mayor nivel, y obviamente la mejor carta de este juego es el legendario Esquilax (un caballo con cabeza de conejo y cuero de caimán). Para mejorar una carta por un nivel, se deben canjear 3 cartas del nivel inmediato inferior, por ejemplo, para obtener un Esquilax de nivel 3, primero debo canjear 3 cartas de Esquilax de nivel 2 (las cuales obviamente desaparecen).
Nuestra amiga intergaláctica Dianita, tiene muchas cartas de distintos niveles del Esquilax, y todas en completo desorden. Tu deber y misión es ayudar a Dianita a saber qué nivel de Esquilax puede llegar a tener como máximo.
Entrada
La entrada consiste en un numero T (1≤T≤500) casos de prueba, cada caso de prueba tiene dos líneas de entrada, la primera línea es un entero N representando la cantidad de cartas de Esquilax que tiene Dianita.
La segunda línea tiene N enteros separados por un espacio, cada uno representa el nivel L de una carta de Esquilax.
(1 ≤ N ≤ 10^7 ) (1 ≤ L ≤ 1000)
Salida
Por cada caso de prueba debes imprimir el nivel máximo de Esquilax que puede conseguir Dianita.
Ejemplo Entrada
3 5 1 1 1 2 2 30 731 731 731 747 731 731 747 731 731 731 731 731 731 731 731 731 731 747 731 731 747 731 731 731 8 871 871 870 870 869 869 869 869
Ejemplo Salida
3 748 872