Деякі натуральні числа (наприклад, \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}.