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 vk. 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 ≤ k ≤ N, se obține calculând cel mai mare divizor comun dk,j pentru fiecare pereche (vk, vj), 1 ≤ j ≤ N, j ≠ k și apoi însumând valorile calculate.

Cerința

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 ≤ N ≤ 200.000
• 1 ≤ vk ≤ 10.000.000, 1 ≤ k ≤ N
• Pentru teste în valoare de 14 puncte N ≤ 2000
• Pentru alte teste în valoare de 5 puncte vk ≤ 2000
• Pentru alte teste în valoare de 39 de puncte vk ≤ 2.000.000

Exemplu:

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 cincilea elev se calculează astfel
(2,6) + (3,6) + (4,6) + (5,6) + (4,6) = 2+3+2+1+2 = 10