Produs

Time limit: 0.1s Memory limit: 8MB Input: produs.in Output: produs.out

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 pp și qq (pqp \leq q) prime între ele există, astfel încât pq=np \cdot q = n. Ajutați-l pe acesta să afle răspunsul cu ajutorul unui program eficient.

Cerinţă

Se dă tt și tt numere naturale nn. Pentru fiecare număr nn, să se afișeze câte perechi pp și qq există cu proprietatea din enunț.

Date de intrare

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

Date de ieşire

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

Restricţii și precizări

  • 1t41051 \leq t \leq 4 \cdot 10^5
  • 1n41061 \leq n \leq 4 \cdot 10^6
  • (p,q)(p, q) și (q,p)(q, p) sunt perechi diferite.
  • Pentru 4040 de puncte n105n \leq 10^5 și testele sunt generate aleatoriu.
  • Pentru 8080 de puncte n106n \leq 10^6.

Exemplu

produs.in

4
1 6 9 7

produs.out

0
4
2
2

Explicație

Pentru 66, cele 44 perechi sunt (1,6)(1, 6), (6,1)(6, 1), (2,3)(2, 3), (3,2)(3, 2).

Log in or sign up to be able to send submissions!