Masala C

Natural son \(n\) daraja son deyiladi, agar shunday natural sonlar \(a\) va \(b\) mavjud bo‘lsa:

• \(a\ge 1\)
• \(b \ge 2\)
• \(n = a^b\)

Masalan:

• \(32 = 2^5\), \(169 = 13^2\), \(1 = 1^2\) — daraja sonlar.
• \(72\), \(2000\), \(31\) — daraja sonlar emas.

Sizga \(N\) va \(M\)  hamda \(N\) ta \(x_1, x_2, ..., x_N\) sonlar beriladi. Har bir \(x_i\)\([1, M]\) oralig‘ida.

Har bir \(x_i\) uchun \([1,M]\) oralig‘idan shunday \(r_i\) sonini topingki:

• \(r_i\) daraja son bo‘lsin;
• \([1,M]\) oralig‘idagi istalgan boshqa daraja son \(p\) uchun quyidagi shart bajarilsin:

\(|x_i - r_i| \le |x_i - p|\)

Ya’ni \(r_i\) — \(x_i\) ga eng yaqin daraja son bo‘lishi kerak.

Birinchi qatorda \(N, M\) beriladi. \((1\le N\le 5000, 10\le M\le 10^{18})\)

Keyingi \(N\) qatorning har birida bittadan \(x_i\) beriladi. \((1\le x_i\le M, 1\le i \le N)\)

\(N\) ta qator chiqaring.

\(i\)-qatorda \(r_i\) ni chiqaring — \(x_i\) ga \([1, M]\) ichidagi eng yaqin daraja son.

Agar \(x_i\) ga eng yaqin son 2 ta bol'sa, ulardan kichigini chiqaring.