Minimal Perfect Square Sum

Given an integer N, your task is to find the minimum number of perfect square numbers which sum to N. A perfect square is an integer that is the square of an integer (e.g. 1, 4, 9, 16, ...). Formally, for a given positive integer \(N\), find the smallest integer \(k\) such that:

\[ N = a_1^2 + a_2^2 + \cdots + a_k^2 \]

subject to the following constraints:

• The number of test cases T must satisfy \(1 \le T \le 10\). If this is not satisfied, output Invalid Test.
• For each test case, the integer N must satisfy \(0 \le N \le 10000\). If a test case does not satisfy this, output Invalid Input for that case.

For each valid test case, output the minimum number of perfect square numbers that sum to N. Each answer should be printed on a new line.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
N1
N2
...
NT

Where:

• T is an integer denoting the number of test cases. It must satisfy \(1 \le T \le 10\).
• Each \(N_i\) (for \(1 \le i \le T\)) is an integer with \(0 \le N_i \le 10000\).

outputFormat

For each test case, output the minimum number of perfect square numbers that sum to N on a new line. If the number of test cases is invalid (i.e. not in the range \(1 \le T \le 10\)), output a single line with Invalid Test. For any test case where \(N\) is out of range, output Invalid Input on that line.

## sample

3
12
0
27

3
0
3

</p>