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.

  • 10T100000
  • 1A1000

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 = 32+12.


hide comments
vineetjai: 2020-09-18 07:35:01

nice problem. precompute efficiently.

surajxd: 2020-08-14 16:15:38

chup @chinmay0402 bc

Last edit: 2020-08-14 16:15:57
chinmay0402: 2020-05-14 06:02:44

Easy one, AC in one go!

mrdevesh_00: 2020-04-27 19:22:06

Easy Question!!

slayer_md: 2020-04-14 14:51:27

AC in ONE GO
Easy ONE

aryan29: 2020-03-31 14:28:29

Easy One:)

cenation007: 2019-06-22 10:48:23

precompute for all n
memoization is must
AC in one go :)

suraj1611: 2019-02-11 19:24:57

Nice problem!

pranjal_rai: 2017-10-19 14:38:08

Can their be multiple square piece of same size?

sagar_zhcet: 2017-06-27 14:58:22

nice problem for the learner of dp like me
enjoyed solving it :)


Added by:BLANKRK
Date:2013-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Code Weavers 2013