didivizori

Un număr natural $x$ se numește freaky dacă și numai dacă are un număr impar de divizori naturali nenuli. De exemplu, $10$ nu este freaky deoarece are $4$ divizori ($1$, $2$, $5$, $10$), dar $9$ este freaky deoarece are $3$ divizori ($1$, $3$, $9$).

Un număr natural $x$ se numește didivizor al unui număr natural $y$ dacă și numai dacă se satisfac următoarele două proprietăți:

• $x$ este freaky;
• $y$ este divizibil cu $x$.

Cerință

Se dă $n$ și un șir $a_1, a_2, \dots, a_n$. Să se afișeze pentru fiecare $i$ de la $1$ la $n$, numărul de didivizori ai lui $a_i$.

Date de intrare

Pe prima linie a fișierului de intrare didivizori.in se află numărul $n$. Pe a doua linie se află șirul $a_1, a_2, \dots, a_n$.

Date de ieșire

Să se afișeze în fișierul didivizori.out răspunsul pentru fiecare $i$ de la $1$ la $n$.

Restricții și precizări

• $1 \leq n \leq 100$
• $1 \leq a_i \leq 10^9$

Exemplu

didivizori.in

11
1 2 3 4 5 6 7 8 9 10 16

didivizori.out

1 1 1 2 1 1 1 2 2 1 3

Explicație

Singurul didivizor al lui $1$ este $1$. Putem verifica că acesta verifică ambele proprietăți.

Singurul didivizor al lui $2$ și al lui $3$ este $1$.

Didivizorii lui $4$ sunt $1$, $4$.

Didivizorii lui $8$ sunt $1$, $4$.

Didivizorii lui $9$ sunt $1$, $9$.

Didivizorii lui $16$ sunt $1$, $4$, $16$.