Cerința

Se dau n numere naturale nenule şi se notează cu P produsul acestora. Să se afle numerele prime din descompunerea lui P în factori primi, precum şi exponentul acestora.

Date de intrare

Fișierul de intrare eratostene5.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 eratostene5.out va conține pe fiecare linie un număr prim din descompunerea lui P şi exponentul acestuia. Factorii primi se vor afişa în ordine crescătoare.

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:

eratostene5.in

4
6 10 21 56

eratostene5.out

2 5
3 2
5 1
7 2

Explicație

Numărul P este 6•10•21•56=25•32•51•72.