Minimum Number of Perfect Squares

Given an integer (M), your task is to determine the minimum number of perfect squares (i.e. numbers that can be expressed as (k^2) for some integer (k), such as 1, 4, 9, 16, ...) that sum up to (M). This is a classic dynamic programming problem where the recurrence relation is given by: (dp[i] = \min_{j^2 \le i}{dp[i - j^2] + 1}) with the base case (dp[0] = 0). The solution should read input from standard input (stdin) and write the corresponding outputs to standard output (stdout).

inputFormat

The first line of input contains a single integer (T), the number of test cases. Each of the following (T) lines contains one integer (M).

outputFormat

For each test case, output on a new line the minimum number of perfect squares that sum up to (M).## sample

3
12
13
4

3
2
1