Zadanie

Ešte to prekontroluj

Počet bodov: 35

Internet je zradné miesto a preto sa z času na čas stane, že nejaká posielaná informácia sa v ňom stratí a nedorazí do určeného cieľa. Takáto strata informácie je o dosť nepríjemnejšia, ak ide o výsledky testovania na COVID-19. Napríklad, laboratórium pošle internetom na vzdialený server informácie o výsledkoch testovania pacientov, no cestou sa niektoré pakety stratia a zoznam pacientov s výsledkami dorazí na server bez niektorých pacientov alebo s chýbajúcimi výsledkami u niektorých.

Toto nebezpečenstvo je ale väčšinou riešené takzvaným kontrolným súčtom dát - checksum. Pred odoslaním dát nad nimi zavoláme nejakú funkciu. Výsledok tejto funkcie pošleme s dátami. Na druhom konci spojenia nad prijatými dátami zavoláme rovnakú funkciu a pozrieme sa, či sa výsledok zhoduje s tým odoslaným. Ak sa zhodujú, dáta sú v poridaku1, inak vieme, že sú poškodené, a môžeme si ich od odosielateľa vyžiadať znova.

Dávid pracujúci v Národnom centre zdravotníckych informácií vymyslel vlastný checksum. Pomôžte mu ho naprogramovať.

Úloha

Poznáte pole čísel reprezentujúcich záznamy o testovaných. Zoberte ľubovoľné dve čísla z poľa a pridajte naspäť ich súčet. Toto opakujte, kým v poli nie je už iba jedno číslo.

Vypíšte najmenší možný súčet všetkých vami pridaných čísel.

Vstup a výstup

Na prvom riadku vstupu sa nachádza číslo \(1 \leq t \leq 10\) udávajúce počet testovaní, pre ktoré je potrebné vyrátať checksum. Nasleduje \(t\) testovaní.

Každé testovanie sa skladá z dvoch riadkov. Na prvom riadku je \(1 \leq n \leq 100\,000\) počet testovaných. V druhom riadku je \(n\) čísel \(1 \leq a_i \leq 1\,000\,000\) oddelených medzerou reprezentujúcich záznamy o testovaných.

Súčet \(n\) v jednom testovacom súbore nepresiahne \(300\,000\).

Pre každé testovanie vypíšte jeho checksum vyrátaný podľa Dávidovho algoritmu.

Príklad

Input:

2
4
1 8 20 21
2
9 7

Output:

88
16

Na vstupe sú dve testovania.

V prvom sme zobrali 1 a 8 a ich súčet sme vložili naspäť. V poli je teraz 9 20 21. Zoberieme 9 a 20 a ich súčet vložíme naspäť. Máme 29 a 21. Nakoniec zoberieme 29 a 21, ich súčet vložíme naspäť. V poli ostane už len 50, vtedy končíme. Súčet nami vložených čísel je 9 + 29 + 50 = 88.

V druhom testovaní sčítame 9 + 7 = 16 a vložíme to naspäť. Ostane nám už iba 16, končíme.

  1. Samozrejme, môže sa stať, že poškodené dáta majú rovnaký checksum ako tie pôbodné. To ale nevadí. Pravdepodobnosť takejto situácie ja rádovo nižšia než toho, že chcecksum odhalí chybu.↩︎

Pre odovzdávanie sa musíš prihlásiť.