== include(page="template/taskheader" task_id="abx") ==

Poveste şi cerinţă...

Un număr natural $n$ se numește putere dacă există două numere naturale $a, b, a ≥ 1, b ≥ 2$ astfel încât $n = ab$. De exemplu, numerele $32, 169, 1$ sunt puteri ({$32 = 2^5^$}, $169 = 13^2^$, $1 = 1^2^$), iar $72$, $2000$ și $31$ nu sunt puteri.
Se citesc numerele naturale $N, M$ și un șir de $N$ numere naturale $x{~1~}, x{~2~}, ..., x{~N~}$ din intervalul $[1, M]$.
Pentru fiecare din cele $N$ numere $x{~i~}$ determinați câte un număr natural $r{~i~}$ din intervalul $[1, M]$, cu proprietatea că $r{~i~}$ este o putere și pentru orice altă putere $p$ din intervalul $[1, M]$ este îndeplinită condiția $|x{~i~} – r{~i~}| ≤ |x{~i~} – p|$, unde $|x|$ reprezintă valoarea absolută a lui $x$ (modulul).
Dacă există două puteri egal depărtate de $x{~i~}$ se va alege puterea cea mai mică. De exemplu pentru numărul $26$, dintre puterile $25$ și $27$ va fi ales numărul $25$.

h2. Date de intrare

Fişierul de intrare $abx.in$ ...

Fișierul de intrare $abx.in$ conține pe prima linie două numere $N$ și $M$, iar pe fiecare dintre următoarele $N$ linii se găsește câte un număr natural $x{~i~}$ ({$1 ≤ i ≤ N$}), cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

h2. Date de ieşire

h2. Date de ieșire

În fişierul de ieşire $abx.out$ ...

Fișierul de ieșire $abx.out$ va conține $N$ linii, pe fiecare linie $i (1 ≤ i ≤ N)$ aflându-se numărul natural $r{~i~}$ cu semnificația din enunț.

h2. Restricţii

h2. Restricții și precizări

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 5000$
* $10 ≤ M ≤ 10^18^$
* Pentru teste valorând $40$ de puncte $M ≤ 5000$
* Pentru teste valorând $70$ de puncte $M ≤ 10^9^$
* $10$ puncte sunt din oficiu (corespund unor teste egale cu exemplul).

h2. Exemplu

table(example). |_. abx.in |_. abx.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example).
   |_. abx.in
    |_. abx.out
      |_. Explicație
|
|    8 1000
345
99
999
500
123
124
99
256
| 343
100
1000
512
121
125
100
256
| 343 = 7^3^
100 = 10^2^
1000 = 10^3^
512 = 2^9^
121 = 11^2^
125 = 5^3^
100 = 10^2^
256 = 2^8^
|

== include(page="template/taskfooter" task_id="abx") ==