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