Задача SumOfPowers

Некоторые натуральные числа (например, 9=3²) сами являются квадратами натуральных чисел; некоторые (например, 17=4²+1²) можно представить как сумму двух квадратов; некоторые (например, 6=2²+1²+1²) — только как сумму минимум трех квадратов; и так далее. Аналогичные подсчеты можно проводить не только для квадратов, но и для других степеней. Например, 17 не является кубом натурального числа и не может быть представлено суммой двух кубов, но может быть представлено суммой трех, как 2³+2³+1³. Напишите программу,  определяющую, в сумму какого минимального количества K-ых степеней натуральных чисел можно разложить каждое из чисел N₁, N₂, …, N_M.

Технические условия:

Программа должна прочитать с клавиатуры сначала показатель степени K (1≤K≤98), затем количество чисел M (1≤M≤9876), для которых нужно найти минимальные количества, затем сами числа N₁, N₂, …, N_M  (каждое 1≤N_i≤987654). Все числа записаны в одной строке и разделены одинарными пробелами. Программа должна вывести на экран в одну строку M разделенных пробелами чисел — минимальные количества K-ых степеней натуральных чисел, в сумму которых можно разложить числа N₁, N₂, …, N_M.

Пример 1:

Ввод:            2 3 9 17 6

Вывод:         1 2 3

Пример 2:

Ввод:            3 3 9 17 6

Вывод:         2 3 6