4068 - Squares   

Status  |  Limits Submit

Description

For any positive integer N , N = a1$scriptstyle wedge$2 + a2$scriptstyle wedge$2 +...+ an$scriptstyle wedge$2 that is, any positive integer can be represented as sum of squares of other numbers.

Your task is to print the smallest `n ' such that N = a1$scriptstyle wedge$2 + a2$scriptstyle wedge$2 +...+ an$scriptstyle wedge$2 .

Input

The first line of the input will contain an integer `t ' which indicates the number of test cases to follow.

Each test case will contain a single integer `N ' (1$ le$N$ le$10000) on a line by itself.

Output

Print an integer which represents the smallest `n ' such that

N = a1$scriptstyle wedge$2 + a2$scriptstyle wedge$2 +...+ an$scriptstyle wedge$2 .

 


Explanation for sample test cases:

 


5 - > number of test cases

1 = 1$scriptstyle wedge$2 (1 term)

2 = 1$scriptstyle wedge$2 + 1$scriptstyle wedge$2 (2 terms)

3 = 1$scriptstyle wedge$2 + 1$scriptstyle wedge$2 + 1$scriptstyle wedge$2 (3 terms)

1 = 2$scriptstyle wedge$2 (1 term)

2 = 5$scriptstyle wedge$2 + 5$scriptstyle wedge$2 (2 terms)

Sample Input  Download

Sample Output  Download

Tags




Discuss