Programacion Competitiva Bolivia

Emparejar peones es un juego que se juega en una cinta de papel dividida
en N celdas que están etiquetadas de 0 a N - 1. Cada celda tiene un numero
arbitrario de peones.

El objetivo del juego es traer el mayor numero de peones a la celda 0. 
Las únicas movidas validas son:

Encontrar un par de peones que compartan una celda digamos X.
Quitar un par de peones de la celda X.
Adicionar un peón a la celda X - 1.
Usted puede realizar tantas movidas como desee en cualquier orden.

Al final se pide mostrar cuantos peones hay en la celda 0.

Entrada

La entrada consiste de múltiples casos de prueba. La primera linea indica 
el numero casos de prueba. Cada caso de prueba tiene dos lineas. La primera 
linea contiene el numero de celda N. La segunda linea contiene N números que 
representan el numero de peones que hay en cada celda.

N <= 1000
La respuesta entra en un entero con signo de 32 bits(int).

Salida

Muestre en una linea cuantos peones hay en la celda 0.

Ejemplos de entrada

6  
2  
0 2  
2  
10 3  
4  
0 0 0 8  
4  
0 1 1 2  
19  
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 123456  
8  
1000 2000 3000 4000 5000 6000 7000 8000  
 
Ejemplos de salida

1  
11  
1  
1  
0  
3921