Problem: A Pythagorean triple is a triple of integer numbers (a, b, c) such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to a, b and c, respectively. An example of the Pythagorean triple is (3, 4, 5).

Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: c = a^2 - b.

Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya's surprise, it actually worked on the triple (3, 4, 5): 5 = 3^2 - 4, so, according to Vasya's formula, it is a Pythagorean triple.

When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers (a, b, c) with 1 ≤ a ≤ b ≤ c ≤ n such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

Input

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

Each test case consists of one line containing one integer n (1 ≤ n ≤ 10^9).

Output

For each test case, print one integer — the number of triples of integers (a, b, c) with 1 ≤ a ≤ b ≤ c ≤ n such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

Example

Input


3
3
6
9


Output


0
1
1

Note

The only Pythagorean triple satisfying c = a^2 - b with 1 ≤ a ≤ b ≤ c ≤ 9 is (3, 4, 5); that's why the answer for n = 3 is 0, and the answer for n = 6 (and for n = 9) is 1.

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
typedef pair<ll,ll> pi;

//__builtin_popcountll(2) (the number of ones in the binary representation)
//__builtin_clz(2) (number of leading zeroes)
//__builtin_ctz(2) (number of trailing zeroes)

/*#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>*/
// s.find_by_order(k)(returns iterator to kth element), s.order_of_key(k)(number of elements less than number)

ll mod = 998244353;
vector<ll> fact(1);
/*vector<ll> spf(1000005);

void spff(){
    int i;
    for(i=1;i<1000005;i++) spf[i] = i;
    for(i=2;i*i<1000005;i++)
    {
        if(spf[i] != i) continue;
        for(int j = i*i; j < 1000005; j+= i){
            if(spf[j]==j) spf[j] = i;
        }
    }
}
while(spf[a[i]]!=a[i]){
              z=spf[a[i]];
              while(a[i]%z==0) a[i]/=z;
              m[z]++;
          }
          if(a[i]>1) m[a[i]]++;*/
 
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);       
}
 
ll power(ll x, ll y) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
        return temp*temp; 
    else
        return x*temp*temp; 
}
 
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1; 
    x = x % p; 
  
    while (y > 0) { 
        if (y & 1) res = (res * x) % p; 
        y = y >> 1;
        x = (x * x) % p; 
    } 
    return res; 
} 
  
ll modInv(ll n, ll p) 
{ 
    return power(n, p - 2, p); 
} 
 
ll ncr(ll n, ll r) {return (n>=r?(fact[n]*modInv(fact[r],mod))%mod*modInv(fact[n-r],mod)%mod:0);}

ll add(ll a, ll b) {ll z=a+b; if(z>=mod) z -= mod; return z;}
ll mul(ll a, ll b) { return (a*b)%mod;}
ll sub(ll a, ll b) { return (a-b+mod)%mod;}
// LLONG_MAX

int main()
{  
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  ll t=1,n,i,j,k;
  cin>>t;
  //fact[0]=1;
  //for(i=1;i<300003;i++)fact[i]=(fact[i-1]*i)%mod;
  while(t--)
  {
      cin>>n;
      ll z=2*(n-1)+1;
      ll c=sqrt(z);
      if(c%2==0) c--;
      cout<<c/2<<'\n';
  }
}