În livezile din jurul orașului Beclean a apărut o nouă specie de pomi fructiferi, care se dezvoltă într-un mod foarte interesant. Astfel, în anul plantării un asemenea pom va produce P fructe. In al doilea an, pentru fiecare divizor propriu D al lui P, pomului îi va crește câte un mugur, care va produce D fructe. În al treilea an, pentru fiecare mugur nou (crescut în anul anterior) se va întâmpla același lucru, și așa mai departe, până când pomul ajunge la maturitate și nu îi mai cresc noi muguri.

De exemplu, dacă P=12, pomul va produce în primul an 12 fructe. În al doilea an, pomului îi vor crește 4 muguri, care vor produce 2, 3, 4, respectiv 6 fructe. În al treilea an, pomului îi vor crește încă trei muguri: unul cu 2 fructe, (datorat divizorului 2 al lui 4) și doi cu 2 și 3 fructe (datorați divizorilor 2 și 3 ai lui 6). Pomul ajunge la maturitate și nu îi cresc alți muguri.

După ce ajunge la maturitate pomul va produce 12+(2+3+4+6)+((2)+(2+3))=34 fructe.

Cerința

Fermierul Petrică are o livadă cu n pomi. Pentru fiecare pom se cunoaște numărul P[i] de fructe produse în primul an. Determinați câte fructe vor produce fiecare pom după ce ajunge la maturitate.

Date de intrare

Fișierul de intrare muguri.in conține pe prima linie numărul n. Pe următoarele n linii se află câte un număr natural nenul P[i], reprezentând câte fructe produce în primul an pomul i.

Date de ieșire

Fișierul de ieșire muguri.out va conține n linii; pe fiecare linie se află un număr, al i-lea număr reprezentând numărul de fructe produse de pomul i după ce ajunge la maturitate.

Restricții și precizări

• n ≤ 5000
• fiecare număr P[i] va fi cel mult egal cu 106;
• pentru 27 de puncte, fiecare număr P[i] va avea exact doi divizori proprii.
• pentru 18 de puncte, fiecare număr P[i] va avea exact trei divizori proprii.

Exemplu:

muguri.in

4
6
5
12
10

muguri.out

11
5
34
17