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.