## 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.