Minimum Number of Squares Sum

Given a positive integer m, you are provided Q queries. Each query contains a positive integer n. You are allowed to select numbers from the set \(\{1, 4, 9, 16, \dots, m^2\}\) (the same number can be selected multiple times) such that their sum is exactly n. Determine the minimum number of numbers required. If it is impossible to form n, output \(-1\).

Note: The set from which you can pick numbers is \(\{1^2, 2^2, \dots, m^2\}\). Since 1 is always available, a solution always exists as long as m is at least 1.

inputFormat

The first line contains two space-separated integers m and Q representing the maximum square index and the number of queries respectively. Each of the following Q lines contains a single positive integer n, representing a query.

outputFormat

For each query, output a single line containing the minimum number of squares required to sum exactly to n. If it is impossible, output \(-1\).

sample

3 3
1
2
30

1
2
5