SumOfPowers
Деякі натуральні числа (наприклад, 9=3^2) самі є квадратами натуральних чисел; деякі (наприклад, 17=4^2+1^2) можна подати як суму двох квадратів; деякі (наприклад, 6=2^2+1^2+1^2) — лише як суму мінімум трьох квадратів; і так далі. Аналогічні підрахунки можна проводити не лише для квадратів, але і для інших степенів. Наприклад, 17 не є кубом натурального числа і не може бути подане сумою двох кубів, але може бути подано сумою трьох, як 2^3+2^3+1^3. Напишіть програму, яка визначає, у суму якої мінімальної кількості K-их степенів натуральних чисел можна розкласти кожне з чисел N_1, N_2, …, N_M.
Вхідні дані
Спочатку задано показник степені K (1 ≤ K ≤ 98), потім кількість чисел M (1 ≤ M ≤ 9876), для яких потрібно знайти мінімальні кількості, потім самі числа N_1, N_2, …, N_M (кожне 1 ≤ N_i ≤ 987654). Усі числа записано у одному рядку і відокремлено одинарними пропусками.
Вихідні дані
Вивести у одному рядку M відокремлених пропусками чисел — мінімальні кількості K-их степенів натуральних чисел, у суму яких можна розкласти числа N_1, N_2, …, N_M.