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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e5+5;

int dp[1005];

int main(){
io;
for(int i = 1;i <= 1000; i++)
dp[i] = INT_MAX;
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= 1000; i++){
for(int j = i;j >= 0; j--){
if((i-(j*j)) >= 0)
dp[i] = min(dp[i], 1 + dp[i - (j*j)]);
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << dp[n] << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
4
1
2
3
10

Output

cmd
1
2
3
2