== include(page="template/taskheader" task_id="rick") ==

După succesul avut cu melodia “Get Schwifty!”, Rick a început să considere posibilitatea unei cariere în muzică. De-a lungul călătoriilor sale inter-dimensionale a strâns o colecţie impresionantă de N sunete. Fiecare sunet este descris prin frecvenţa sa, măsurată în BPM (beats per minute).

După succesul avut cu melodia “Get Schwifty!”, Rick a început să considere posibilitatea unei cariere în muzică. De-a lungul călătoriilor sale inter-dimensionale a strâns o colecţie impresionantă de $N$ sunete. Fiecare sunet este descris prin frecvenţa sa, măsurată în BPM (beats per minute).

Rick a inventat un dispozitiv care, având la dispoziţie o mulţime de N sunete, alege aleator o submulţime a acestei mulţimi. Sunetele acestei submulţimi sunt combinate, rezultând o melodie. Calitatea unei melodii este dată de cel mai mare divizor comun al frecvenţelor sunetelor combinate. Rick nu este niciodată mulţumit de melodia obţinută aşa că mereu resetează dispozitivul pentru a obţine alte melodii.

Rick a inventat un dispozitiv care, având la dispoziţie o mulţime de $N$ sunete, alege aleator o submulţime a acestei mulţimi. Sunetele acestei submulţimi sunt combinate, rezultând o melodie. Calitatea unei melodii este dată de cel mai mare divizor comun al frecvenţelor sunetelor combinate. Rick nu este niciodată mulţumit de melodia obţinută aşa că mereu resetează dispozitivul pentru a obţine alte melodii.

h2. Cerinţă

Rick e mulţumit să găsească suma calităţilor tuturor submulţimilor posibile din mulţimea de N sunete.

Rick e mulţumit să găsească suma calităţilor tuturor submulţimilor posibile din mulţimea de $N$ sunete.

h2. Date de intrare

Prima linie a fişierului $rick.in$ va conţine numărul natural N, cu semnificaţia din enunţ.
A doua linie va conţine N numere naturale, reprezentând frecvenţele sunetelor din colecţia lui Rick.

Prima linie a fişierului $rick.in$ va conţine numărul natural $N$, cu semnificaţia din enunţ.
A doua linie va conţine $N$ numere naturale, reprezentând frecvenţele sunetelor din colecţia lui Rick.

h2. Date de ieşire

h2. Restricţii

* 1 ≤ N ≤ 500.000
* 1 ≤ frecvenţele sunetelor ≤ 500.000
* pentru 15% din punctaj 1 ≤ N ≤ 20
* pentru alte 25% din punctaj 1 ≤ N, diferenţa în modul dintre oricare două frecvenţe ≤ 1.000
* pentru alte 35% din punctaj 1 ≤ N, frecvenţele sunetelor ≤ 100.000

* $1 ≤ N ≤ 500.000$
* $1 ≤ frecvenţele sunetelor ≤ 500.000$
* pentru $15%$ din punctaj $1 ≤ N ≤ 20$
* pentru alte $25%$ din punctaj $1 ≤ N$, diferenţa în modul dintre oricare două frecvenţe $≤ 1.000$
* pentru alte $35%$ din punctaj $1 ≤ N$, frecvenţele sunetelor $≤ 100.000$

* prin probabilitate uniformă înţelegem că orice submulţime are aceeaşi probabilitate să fie extrasă de către dispozitiv

* considerăm că submulţimea vidă are cel mai mare divizor comun 1

* considerăm că submulţimea vidă are cel mai mare divizor comun $1$

h2. Exemplu