Некоторые натуральные числа (например, \textbf{9}=\textbf{3^2}) сами являются квадратами натуральных чисел; некоторые (например, \textbf{17}=\textbf{4^2+1^2}) можно представить как сумму двух квадратов; некоторые (например, \textbf{6}=\textbf{2^2+1^2+1^2}) --- только как сумму минимум трех квадратов; и так далее. Аналогичные подсчеты можно проводить не только для квадратов, но и для других степеней. Например, \textbf{17} не является кубом натурального числа и не может быть представлено суммой двух кубов, но может быть представлено суммой трех, как \textbf{2^3+2^3+1^3}. Напишите программу, определяющую, в сумму какого минимального количества \textbf{K}-ых степеней натуральных чисел можно разложить каждое из чисел \textbf{N_1}, \textbf{N_2}, …, \textbf{N_M}. \InputFile Сначала задан показатель степени \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{98}), затем количество чисел \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{9876}), для которых нужно найти минимальные количества, затем сами числа \textbf{N_1}, \textbf{N_2}, …, \textbf{N_M} (каждое \textbf{1} ≤ \textbf{N_i} ≤ \textbf{987654}). Все числа записаны в одной строке и разделены одинарными пробелами. \OutputFile Вывести в одну строку \textbf{M} разделенных пробелами чисел --- минимальные количества \textbf{K}-ых степеней натуральных чисел, в сумму которых можно разложить числа \textbf{N_1}, \textbf{N_2}, …, \textbf{N_M}.