Cerința

Se dau n numere naturale nenule. Aflaţi pentru fiecare număr dat x, câte numere naturale nenule mai mici sau egale cu x sunt prime cu x?

Date de intrare

Fișierul de intrare eratostene3.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 eratostene3.out va conține pentru fiecare număr x din fişierul de intrare, numărul de numere naturale nenule mai mici sau egale cu x, prime cu x.

Restricții și precizări

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

Exemplu:

eratostene3.in

3
4 7 12

eratostene3.out

2 6 4

Explicație

Numerele prime cu 4, mai mici sau egale cu 4, sunt: 1,3.
Numerele prime cu 7, mai mici sau egale cu 7, sunt: 1,2,3,4,5,6.
Numerele prime cu 12, mai mici sau egale cu 12, sunt: 1,5,7,11.
Vezi Indicatorul lui Euler.