Let's call an array a consisting of n positive (greater than 0) integers beautiful if the following condition is held for every i from 1 to n: either a_i = 1, or at least one of the numbers a_i - 1 and a_i - 2 exists in the array as well.

For example: 

  * the array [5, 3, 1] is beautiful: for a_1, the number a_1 - 2 = 3 exists in the array; for a_2, the number a_2 - 2 = 1 exists in the array; for a_3, the condition a_3 = 1 holds; 
  * the array [1, 2, 2, 2, 2] is beautiful: for a_1, the condition a_1 = 1 holds; for every other number a_i, the number a_i - 1 = 1 exists in the array; 
  * the array [1, 4] is not beautiful: for a_2, neither a_2 - 2 = 2 nor a_2 - 1 = 3 exists in the array, and a_2 ≠ 1; 
  * the array [2] is not beautiful: for a_1, neither a_1 - 1 = 1 nor a_1 - 2 = 0 exists in the array, and a_1 ≠ 1; 
  * the array [2, 1, 3] is beautiful: for a_1, the number a_1 - 1 = 1 exists in the array; for a_2, the condition a_2 = 1 holds; for a_3, the number a_3 - 2 = 1 exists in the array. 



You are given a positive integer s. Find the minimum possible size of a beautiful array with the sum of elements equal to s.

Input

The first line contains one integer t (1 ≤ t ≤ 5000) — the number of test cases.

Then t lines follow, the i-th line contains one integer s (1 ≤ s ≤ 5000) for the i-th test case.

Output

Print t integers, the i-th integer should be the answer for the i-th testcase: the minimum possible size of a beautiful array with the sum of elements equal to s.

Example

Input


4
1
8
7
42


Output


1
3
3
7

Note

Consider the example test:

  1. in the first test case, the array [1] meets all conditions; 
  2. in the second test case, the array [3, 4, 1] meets all conditions; 
  3. in the third test case, the array [1, 2, 4] meets all conditions; 
  4. in the fourth test case, the array [1, 4, 6, 8, 10, 2, 11] meets all conditions. 
#include <bits/stdc++.h>
#include<cstdio>
using namespace std;

//why are you looking at my code? ತಎತ
//ok i admit my codes are just dumbdumb I'm sOrRy_(:3」∠)_

using str = string; // yay python!
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector <ll> vl;
typedef pair<ll,ll> pl;
#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)size(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

void setIO(string name=""){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if((int)name.size() > 0){freopen((name+".in").c_str(), "r", stdin); freopen((name+".out").c_str(), "w", stdout);}
}
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mod=1000000007;

//-------------------####Real Programming###------------------


void solve(){
  int n; cin>>n;
  int dp[n]; dp[1]=1;
  FOR(i,2,n+1){
    if(pow((int)sqrt(i-1),2)==(i-1)){
      dp[i]=dp[i-1]+1;
    }else dp[i]=dp[i-1];
  }
  //FOR(i,1,n+1) cout<<dp[i]<<" ";
  cout<<dp[n]<<"\n";
}
int main(){
  setIO("");
  int t; cin>>t; while(t--)
  solve();
  return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/