Algorithm of 11407 - Squares

Problem Description Link
Algorithm:

This is a simple problem  to solve this problem you can pre generate the number of minimum terms for all integer from 1 to 10000 and get input and check from array how many  term needed and print the value.

Process:

 For any positive integer N , N = a12 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.

For example you know minimum term of 1,2,3,4 and based on this value calculate others  5 to 10000 value term

1

2

3

1

2

3

4

2

1

2

1                    2                        3              4                              5              6              7                              8              9              10

For 5

S=sqrt(5)=2

Way    2²+1²=5 so 2 term

And  1²+2²=5 so 2 term

Min value=2

So

Solution of 11407 - Squares

Problem Description
source: http://uva.onlinejudge.org/external/114/11407.html

For any positive integer N, N = a 2 1 + a 2 2 + . . . + a 2 n 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 = a 2 1 + a 2 2 + . . . + a 2 n.

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 ≤ N ≤ 10000) on a line by itself.