Enchufes Eléctricos
Roy acaba de mudarse a un nuevo apartamento. Bueno, en realidad el apartamento en sí no es muy nuevo, incluso se remonta a los días antes de que la gente tuviera electricidad en sus casas. Debido a esto, el apartamento de Roy tiene solo un tomacorriente de pared, por lo que Roy solo puede encender uno de sus electrodomésticos a la vez.
A Roy le gusta ver la televisión mientras trabaja en su computadora y escuchar su equipo de música (a un volumen alto) mientras se refresca, por lo que usar un solo tomacorriente no es una opción. En realidad, quiere tener todos sus electrodomésticos conectados a una toma de corriente, todo el tiempo. La respuesta, por supuesto, son las regletas de enchufes, y Roy tiene algunas viejas que usó en su antiguo apartamento. Sin embargo, ese apartamento tenía muchos más enchufes de pared, por lo que no está seguro de si sus regletas de enchufes le proporcionarán suficientes enchufes ahora.
Su tarea es ayudar a Roy a calcular cuántos electrodomésticos puede proporcionar con electricidad, dado un conjunto de enchufes múltiples. Tenga en cuenta que sin regletas de enchufes, Roy puede alimentar un solo electrodoméstico a través del tomacorriente de pared. Además, recuerde que una regleta de enchufes está alimentada y es de utilidad, si está conectada al tomacorriente de pared, o conectada a un enchufe de otra regleta que ya se encuentra alimentada.
Entrada
La entrada comenzará con un solo entero , lo que indica el número de casos de prueba a seguir. Luego siguen líneas, cada una de las cuales describe un caso de prueba. Cada caso de prueba comienza con un número entero , que indica el número de regletas en el caso de prueba. Luego siguen, en la misma línea, números enteros separados por espacios simples, , ,..., donde , indica el número de enchufes en cada regleta.
Salida
La salida de una línea por caso de prueba, con el número máximo de dispositivos que se pueden alimentar.
Ejemplo de Entrada
3
3 2 3 4
10 4 4 4 4 4 4 4 4 4 4
4 10 10 10 10
Ejemplo de Salida
7
31
37
Comments
Un problema para pensar un rato. ¡Recomendadísimo!