powall

Definim o putere ca fiind un număr natural $P$ cu proprietatea că există alte două numere naturale $A > 1$ și $B > 1$ astfel încât $P = A^B$. Exemple de puteri: $8 = 2^3$; $625 = 5^4$; $7776 = 6^5$.

Cerință

Fie $N$ un număr natural și $V$ un șir de $N$ numere naturale $V = (V_1, V_2, \ldots, V_N)$.

Să se scrie un program care determină un număr natural $X$, cu proprietatea că numerele din $(X \cdot V_1, X \cdot V_2, \ldots, X \cdot V_N)$, devin simultan puteri.

Date de intrare

Fișierul de intrare powall.in conține pe prima linie un număr natural $N$, iar pe a doua linie $N$ numere naturale $V_i$, $1 \leq i \leq N$, despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire este powall.out.

Numărul căutat $X$ va fi scris în fișierul de ieșire descompus în factori primi, după cum urmează:

• Pe prima linie se va scrie un număr $F$, reprezentând numărul de factori primi ai lui $X$.
• Pe fiecare din următoarele $F$ linii se va scrie câte o pereche de numere naturale $B$ și $E$ ($B > 1$ și $E > 0$, unde $B$ reprezintă un factor prim, iar $E$ reprezintă exponentul lui $B$, din descompunerea în factori primi ai numărului $X$), despărțite prin câte un spațiu.

Restricții și precizări

• $2 \leq N \leq 10$
• $2 \leq V_i < 10^{12}$ , $1 \leq i \leq N$
• Ordinea scrierii perechilor $(B, E)$ nu este importantă;
• Nu se acceptă decât perechi $(B, E)$ pentru care $B$ este un factor prim al descompunerii a cel puțin unuia dintre numerele $V_i$, $1 \leq i \leq N$;
• Oricare două perechi $(B, E)$ trebuie să aibă valorile $B$ distincte.
• Se acceptă doar soluții pentru care ambele valori $(B, E) \leq 2^{60}$;
• Se garantează că există soluție

Exemplu

powall.in

3
2 3 6

powall.out

2
2 9
3 14

Explicație

$N = 3$ și $V = (2, 3, 6)$

O solție posibilă este $X = 2448880128 = 2^9 \cdot 3^{14}$.

$X \cdot V = (2^{10} \cdot 3^{14}, 2^9 \cdot 3^{15}, 2^{10} \cdot 3^{15}) = ((2^5 \cdot 3^7)^2, (2^3 \cdot 3^5)^3), (2^2 \cdot 3^3)^5)$.