pericol

Avem o clasă cu $N$ elevi inventivi. Pentru fiecare dintre ei se cunoaşte un coeficient de atitudine reprezentat printr-un număr natural nenul $v_k$. Interacţiunile din cadrul grupului de elevi al clasei produc efecte secundare importante şi conducerea şcolii a definit o mărime scalară numită indicator de pericol care măsoară influenţa pe care un elev o are asupra celorlalţi elevi din clasă. Indicatorul de pericol asociat elevului $k$, $1 \leq k \leq N$, se obţine calculând cel mai mare divizor comun $d_{k,j}$ pentru fiecare pereche $(v_k, v_j)$, $1 \leq j \leq N$, $j \neq k$ şi apoi însumând valorile calculate.

Cerință

Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.

Date de intrare

În fişierul text pericol.in pe prima linie se află numărul natural $N$. Pe a doua linie se află $N$ numere naturale nenule, separate prin câte un spaţiu, reprezentând coeficienţii de atitudine ai celor $N$ elevi.

Date de ieșire

În fişierul text pericol.out se vor scrie, pe prima linie, $N$ numere naturale, separate prin câte un spaţiu, al $k$-lea număr natural reprezentând indicatorul de pericol asociat celui de-al $k$-lea elev.

Restricții și precizări

• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq v_k ≤ 10^7, 1 \leq k \leq N$

Exemplul

pericol.in

6
2 3 4 5 6 4

pericol.out

8 7 10 5 10 10

Explicație

De exemplu, indicatorul de pericol al celui de-al $5$-lea elev se calculează astfel:
$(2, 6) + (3, 6) + (4, 6) + (5, 6) + (4, 6) = 2 + 3 + 2 + 1 + 2 = 10$