abx

Un număr natural $n$ se numește putere dacă există două numere naturale $a$, $b$, $a \geq 1$, $b \geq 2$ astfel încât $n = a^b$. 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, \dots, x_N$ din intervalul $[1,M]$.

Cerință

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| \leq |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$.

Date de intrare

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 \leq i \leq N$), cu semnificația de mai sus.
Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

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

Restricții și precizări

• $1 \leq N \leq 5\ 000$
• $10 \leq M \leq 10^{18}$
• Pentru teste valorând 40 de puncte, $M \leq 5\ 000$.
• Pentru teste valorând 70 de puncte, $M \leq 10^9$.

Exemplu

abx.in

8 1000
345
99
999
500
123
124
99
256

abx.out

343
100
1000
512
121
125
100
256

Explicație

$343 = 7^3$
$100 = 10^2$
$1\ 000 = 10^3$
$512 = 2^9$
$121 = 11^2$
$125 = 5^3$
$100 = 10^2$
$256 = 2^8$