Cerința

Se dau n numere naturale. Aflaţi pentru fiecare număr câţi factori primi are în descompunere.

Date de intrare

Fișierul de intrare eratostene2.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene2.out va conține pe prima linie n numere, fiecare reprezentând numărul factorilor primi din descompunerea numărului corespunzător din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:

eratostene2.in

7
30 5 44 210 1 35 30030

eratostene2.out

3 1 2 4 0 2 6

Explicație

Numerele date se descompun astfel: 30=2•3•5 , 5=5 , 44=22•11 , 210=2•3•5•7, 1=1, 35=5•7 , 30030=2•3•5•7•11•13.