C - 2048

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

Poznáte hru 2048?
Kartičky s priradenými hodnotami stoja v rade. V každom kroku môžete urobiť jednu z dvoch vecí:

zdvojnásobiť hodnotu jednej z kartičiek
zobrať dve susedné kartičky s rovnakou hodnotou a zlúčiť ich do jednej s ich súčtom

Vašou úlohou je dostať na konci jednu kartičku s čo najmenšou hodnotou.

Úloha

Pre danú postupnosť ohodnotení kartičiek zistite, akú najmenšiu hodnotu vieme dostať na konci.

V prvom riadku súboru sa nachádza číslo Q udávajúce počet sád.

Nasleduje Q riadkov s počtom kartičiek N a N hodnotami kartičiek K_i v poradí ako sú zoradené za sebou v rade.
1 ≤ Q ≤ 129

1 ≤ N ≤ 257
K=2ⁱ,0 ≤ i ≤ 11, i∈Z

Výstupom programu je odpoveď pre každú sadu na samostatnom riadku.

3
1 2048
2 1024 2048
3 1 1 1

2048
4096
4