Training Land of Fury
All submissions for this problem are available.
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 area of land. In order to minimize the expenditure, Fury has to buy minimum number of pieces of land. Help Fury by determining the minimum number of pieces that should be bought.
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.
For each test case print the minimum number of pieces that should be bought.
- 10 ≤ T ≤ 100000
- 1 ≤ A ≤ 1000
Input: 4 1 2 3 10 Output: 1 2 3 2
For the last test case 10 the answer will be 2 as 10 can
be expressed as sum of minimum two squares that is
10 = 32+12 .
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, CS2|
Fetching successful submissions