P8447 "FAOI-R1" Perfect Squares.

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$.)

**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$.

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

**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$.** ------------ | Test Point ID | $m \le$ | $n \le$ | Score | | :--: | :--: | :--: | :--: | | $1$ | $30$ | $10^4$ | $40$ | | $2 \sim 3$ | $30$ | $10^{18}$ | $15 \times 2$ | | $4 \sim 9$ | $500$ | $10^{18}$ | $5 \times 6$ | 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