Editing 3763 - Puternic (section)

==Cerința==

Un număr puternic este un număr natural mai mare decât 1 care are proprietatea că dacă este divizibil cu numărul prim '''p''' atunci este divizibil și cu '''p^2'''. De exemplu, 36 și 27 sunt numere puternice, în timp ce 12 nu este număr puternic deoarece este divizibil cu 3 și nu este divizibil cu '''3^2'''. La ora de matematică elevii au aflat ce înseamnă un număr puternic. Pentru a verifica dacă elevii au înțeles, domnul profesor a scris pe tablă un șir de '''N''' numere naturale '''X1, X2, …, XN''' și l-a rugat pe Mihai să șteargă din șir numerele puternice.

Analizând numerele rămase, Mihai a observat că se poate obține un număr puternic prin concatenarea a două numere din șirul rămas, numere egal depărtate de capetele acestui nou șir. Concatenarea presupune lipirea numărului din a doua jumătate a șirului la finalul celui aflat în prima jumătate. Dacă noul șir are număr impar de elemente, elementul din mijloc se ignoră. De exemplu, dacă șirul obținut după ștergerea numerelor puternice este: 12, 1, 19, 13, 3, 21, 5 atunci numerele obținute prin concatenare sunt 125, 121, 193.
Scrieți un program care citește un număr natural N și apoi un șir de N numere naturale și determină:

Câte numere puternice sunt în șirul dat;
Care sunt perechile de numere din șirul rămas după ștergerea numerelor puternice, numere egal departate de capetele șirului, prin concatenarea cărora se obține un număr puternic.