CCEX Suceava 2023 - clasa a VI-a | Produs

Andrei este un elev pasionat la informatică. Astăzi a învățat despre cel mai mare divizor comun a două numere și are ca temă să afle câte perechi de numere $p$ și $q$ ($p \leq q$) prime între ele există, astfel încât $p \cdot q = n$. Ajutați-l pe acesta să afle răspunsul cu ajutorul unui program eficient.

Cerinţă

Se dă $t$ și $t$ numere naturale $n$. Pentru fiecare număr $n$, să se afișeze câte perechi $p$ și $q$ există cu proprietatea din enunț.

Date de intrare

Fișierul de intrare produs.in conține pe prima linie numărul $t$. Pe a doua linie se vor afla $t$ numere naturale.

Date de ieşire

Fișierul de ieșire produs.out conține $t$ linii, pe linia $i$ aflându-se răspunsul de la al $i$-lea număr.

Restricţii și precizări

• $1 \leq t \leq 4 \cdot 10^5$
• $1 \leq n \leq 4 \cdot 10^6$
• $(p, q)$ și $(q, p)$ sunt perechi diferite.
• Pentru $40$ de puncte $n \leq 10^5$ și testele sunt generate aleatoriu.
• Pentru $80$ de puncte $n \leq 10^6$.

Exemplu

produs.in

4
1 6 9 7

produs.out

0
4
2
2

Explicație

Pentru $6$, cele $4$ perechi sunt $(1, 6)$, $(6, 1)$, $(2, 3)$, $(3, 2)$.