Problema número 741

Castillos de naipes

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Castillo de naipes de 4 pisos

Debido a la ascendencia británica de mi abuela, en la familia hay mucha afición al bridge. Cada vez que se ponen a jugar empiezan a decir cosas extrañas como subasta, tres sin triunfo, ser el muerto o slam. Yo no entiendo nada. Solo espero pacientemente a que llegue la hora del té y dejen de jugar, para coger las cartas y ponerme a hacer castillos, que es lo que me gusta.

Para montarlos, empiezo colocando varias parejas de cartas formando triángulos consecutivos que recuerdan a una sucesión de letras A sin la línea horizontal del centro. Encima, entre cada par de triángulos, pongo una carta que hace las veces de "suelo" para el siguiente nivel, y repito el procedimiento, con un triángulo menos que en el piso previo. Después de un rato llego a la cúspide, con un único triángulo.

A veces hago un mal movimiento y se me desmorona todo el castillo. Pero lo que peor llevo es cuando, a mitad del montaje, me quedo sin cartas y se queda a mitad mi gran obra.

Entrada

El primer número de la entrada indica cuántos casos de prueba deberán ser procesados. Cada uno está compuesto por un número 1 ≤ n ≤ 800.000.000 indicando el número de pisos del castillo que se quiere construir.

Salida

Por cada caso de prueba se escribirá el número de cartas necesario para construir el castillo de la altura indicada, siguiendo la distribución de naipes descrita.

Entrada de ejemplo

4
1
2
4
50000

Salida de ejemplo

2
7
26
3750025000