Keď Andrej robil pravidelnú údržbu KSP-áckich agentov, zistil jednu hroznú vec. Každý z nich má taký procesor, ktorý má prvočíselný počet jadier! Takáto architektúra je už dávno zastaraná. Dnes sa takmer vždy používajú procesory, ktorých počet jadier je zložené číslo, pretože dokážu oveľa efektívnejšie paralelizovať úlohy.

Andrej teda nemá inú možnosť, ako nakúpiť do eráru nových agentov. Lenže čo urobí s tými starými? Krtko mu našťastie poradil výborný nápad: niektoré z nich môže použiť na ťaženie bitcoinu a zvyšné predať na Bazoši.

Úloha

Za každý počítač, čo predá, zarobí Trojsten toľko peňazí, koľko mal ten počítač jadier. Zároveň, celkový výkon počítačov, ktoré ťažia bitcoin, je súčin počtov jadier v každom počítači. Keďže Andrej je pedant, nepripustí, aby zárobok z predaja bol iný ako výkon na ťaženie. Zároveň je zjavné, že všetci chcú aby bol zárobok (a teda aj celkový výkon) čo najväčší. Aký najväčší môže byť?

Formát vstupu

V prvom riadku vstupu je číslo $t$ ($1 \leq t \leq 100$) udávajúce počet testov. Nasleduje $t$ testov, pričom každý má nasledujúci formát:

V prvom riadku testu je číslo $n$ ($1 \leq n \leq 95$). Nasleduje $n$ riadkov, pričom na $i$-tom z nich je prvočíslo $p_i$ ($p_i \leq 499$), a celé číslo $k_i$ ($1 \leq k_i \leq 10^{15}$), ktoré vyjadrujú, že v erári je $k_i$ agentov s $p_i$-jadrovým procesorom.

Označme $k$ celkový počet počítačov, $m$ celkový počet jadier a $P$ najväčší počet jadier v počítači. Formálne: $$ k = \sum_{i=1}^{n} k_i $$ $$ m = \sum_{i=1}^{n} p_i k_i $$

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Na vstup vypíšte $t$ riadkov. Pre každý test vypíšte maximálny možný zárobok (rovnaký ako výkon), ktorý sa dá dosiahnuť alebo $0$, ak počítače nemožno rozdeliť tak, aby bol zárobok rovný výkonu.

Príklad

4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7

25
17
0
8

V prvom teste je optimálne riešenie predať počítače s procesormi $2+2+3+7+11=25$ a bitcoin ťažiť s procesormi $5 \times 5 = 25$.

V druhom teste jeden počítač predáme a druhý necháme ťažiť.

V treťom teste neexistuje spôsob, ako rozdeliť počítače tak, aby zárobok a výkon bol rovnaký (musíme sa zbaviť všetkých počítačov).

V štvrtom predáme $4$ počítače a zvyšné $3$ ťažia: $2+2+2+2=2 \times 2 \times 2$.