Problem Description

Given a positive integer $m$. There are $Q$ queries. In each query, a positive integer $n$ is given. You need to pick some numbers from $1,4,9,16,\ldots,m^2$ (the same number may be picked multiple times) such that their sum is exactly $n$. Find the minimum number of picked numbers. (If there is no solution, output $-1$.)

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

The first line contains two positive integers $m, Q$.

The next $Q$ lines each contain one positive integer $n$.

Output Format

For each query in each test case, output one line with one positive integer, which is the answer.

5
1 5
1
2
3
4
5
5 5
8
20
25
37
49
11 1
179
13 1
507
19 1
841

1
2
3
4
5
2
2
1
4
4
3
3
4

Hint

Sample explanation:

For the first test case, obviously the answer is $n$, because you can only pick $1$.

For the second test case:

• $8 = 2^2 + 2^2$;
• $20 = 4^2 + 2^2$;
• $25 = 5^2$;
• $37 = 5^2 + 2^2 + 2^2 + 2^2$; (or $37 = 4^2 + 4^2 + 2^2 + 1^2$)
• $49 = 5^2 + 4^2 + 2^2 + 2^2$; (or $49 = 4^2 + 4^2 + 4^2 + 1^2$)
• Note that $37 = 6^2 + 1^2$ and $49 = 7^2$ are both invalid, because in this test case $m = 5$.

For $100\%$ of the testdata, $1 \le T \le 30$, $1 \le Q \le 10^4$, $1 \le m \le 500$, $1 \le n \le 10^{18}$. In a single test point, the sum of $m$ over all test cases ($\sum m$) satisfies $1 \le \sum m \le 500$.

Translated by ChatGPT 5