SumOfPowers
Some natural numbers, like 9 (3^2), are perfect squares of natural numbers. Others, such as 17 (4^2+1^2), can be expressed as the sum of two squares. Some numbers, like 6 (2^2+1^2+1^2), require at least three squares to be represented. This concept extends beyond squares to other powers as well. For instance, 17 is not a cube of a natural number and cannot be expressed as a sum of two cubes, but it can be represented as a sum of three cubes: 2^3+2^3+1^3. Your task is to write a program that determines the minimum number of K-th powers of natural numbers needed to express each of the numbers N_1, N_2, …, N_M.
Input
First, you are given the exponent K (1 ≤ K ≤ 98), followed by the number of numbers M (1 ≤ M ≤ 9876) for which you need to find the minimum numbers. Then, the numbers themselves are provided: N_1, N_2, …, N_M (each 1 ≤ N_i ≤ 987654). All numbers are given on one line, separated by single spaces.
Output
Output a single line containing M numbers, separated by spaces, representing the minimum number of K-th powers of natural numbers required to express each of the numbers N_1, N_2, …, N_M.