NFURY  Training Land of Fury
S.H.I.E.L.D. is recruiting soldiers for the battle with Loki's army. Nick Fury has come to Manhattan to find a large area of land to be used for training purposes. He meets a popular landlord there who is a little foolish by nature.
He gives square pieces of land with integral sides and charges on the basis of number of pieces of land bought irrespective of how large a piece of land is. Fury has to buy exactly A square units of land. Help Fury by determining the minimum number of pieces that should be bought in order to minimize the expenditure.
Input
The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains a single integer A denoting the area that nick fury want to buy.
 10 ≤ T ≤ 100000
 1 ≤ A ≤ 1000
Output
For each test case print the minimum number of pieces that should be bought.
Example
Input: 4 1 2 3 10 Output: 1 2 3 2
Explanation
For the last test case 10 the answer will be 2. 10 can be expressed as sum of minimum two squares that is 10 = 3^{2}+1^{2}.
hide comments
suraj1611:
20190211 19:24:57
Nice problem! 

pranjal_rai:
20171019 14:38:08
Can their be multiple square piece of same size? 

sagar_zhcet:
20170627 14:58:22
nice problem for the learner of dp like me


anurag44:
20170616 17:10:53
nyc prblm..


akshayvenkat:
20160707 07:21:32
AC in one go :D 

singh1495:
20160614 17:49:27
easy dp just apply precomputation.............. love u dp....... 

KD :
20160528 10:02:20
1st dp >AC in go :P 

nihil_5596:
20160113 20:39:14
1st time AC in 1 go! :) 

mr_lazy:
20150808 22:26:44
Cake walk question :P 

Scape:
20150725 17:36:05
What is the purpose of setting T <= 10^5 when A <= 10^3? Why not make the other way around? 
Added by:  BLANKRK 
Date:  20131114 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Code Weavers 2013 