SumOfPowers#2687
Some natural numbers, such as 9 = 3^2, are perfect squares of natural numbers. Others, like 17 = 4^2 + 1^2, can be represented as the sum of two squares. Some, for example 6 = 2^2 + 1^2 + 1^2, require at least three squares for their representation, and so on. Such calculations can be carried out not only for squares but also for other powers. For example, is not the cube of a natural number and cannot be expressed as the sum of two cubes, but it can be represented as the sum of three cubes: 2^3 + 2^3 + 1^3. Write a program to determine the minimum number of -th powers of natural numbers whose sum equals each of the numbers N_1, N_2, \ldots, N_M.
First, the exponent (1 \leq K \leq 98) is given, followed by the number of values (1 \leq M \leq 9876) that require calculation. Then the numbers themselves are given: N_1, N_2, \ldots, N_M (each 1 \leq N_i \leq 987654). All values are given on a single line, separated by single spaces.
Print a single line with numbers separated by spaces—the minimum number of -th powers of natural numbers whose sum equals each of the respective numbers N_1, N_2, \ldots, N_M.
Example 1