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;
#define SZ(a) (int((a).size()))
#define FOR(i,n) for(int _n=(n),i=0;i<_n;++i)
#define FORI(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define FORSZ(i,c) FOR(i,SZ(c))
#define SET(t,x) memset((t),(x),sizeof(t))
#define FOREACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)  // Might also use for(auto &x : c)
#define PRINT(x) cout<<#x<<"="<<x<<"\n"
#define PRINTI(x,n) for(__typeof(n)i=0;i<(n);++i)cout<<(x)[i]<<" ";cout<<"\n"
#define PRINTIJ(x,n1,n2) for(__typeof(n1)i=0;i<(n1);++i,cout<<"\n")for(__typeof(n2)j=0;j<(n2);++j)cout<<(x)[i][j]<<" ";cout<<"\n"
#define ALL(c) begin(c), end(c)
#define RALL(c) rbegin(c), rend(c)
#define PRESENT(c,x) ((c).find(x) != (c).end())
#define CPRESENT(c,x) (find(ALL(c),x) != (c).end())
#define ABS(a) ( (a) >= 0 ? (a) : (-(a)))
#define PB push_back
#define EB emplace_back  // EB is almost always preferable to PB. Doesn't make extra copies. Use .EB(x) or .EB(x,y) for pairs/tuples. Note: .EB(x,y) is better than .EB({x,y}).
#define MP make_pair
#define EPS 1e-11
#define EPS2 1e-9
#define D_EQ(a,b) ((a)>((b)-EPS) && (a)<((b)+EPS))
#define D_LT(a,b) ((a)<((b)-EPS))
#define D_LTEQ(a,b) ((a)<((b)+EPS))
#define D_GT(a,b) ((a)>((b)+EPS))
#define D_GTEQ(a,b) ((a)>((b)-EPS))
#define INF 100000000
#define ALLTRUE(f,x) ({bool flag=true;f if(!(x)) {flag=false;break;};flag;})  // e.g. if(ALLTRUE(FORSZ(i,v1), v1[i]%2==0));  // Can be replaced with all_of and lambda: if(all_of(ALL(v), [](auto &x){return x>0;}))
#define ONETRUE(f,x) ({bool flag=false;f if(x) {flag=true;break;};flag;}) // can be replaced with any_of and lambda.
#define COUNT(f,x) ({int cnt=0;f cnt+=(x);cnt;})  // e.g. int ctr = COUNT(FOR(i,N), v[i]>0); // Can be replaced with count_if and lambda.
#define getint() ({int e=0;for(gets(q=s);*q;)e=(e<<3)+(e<<1)+*q++-48;e;})
#define putint(a) ({int tmp=a,tmp2;*(q=s+10)='\0';for(;;){tmp2=tmp/10;*--q=tmp-(tmp2<<3)-(tmp2<<1)+48;tmp=tmp2;if(!tmp)break;}puts(q);})

typedef long long ll;
//typedef __int128 int128;  // Linux GCC/g++ supports __int128. MinGW gcc/g++ does not.
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<ll> VLL;
typedef vector<PII> VPII;
typedef vector<string> VS;
typedef vector<VI> VVI;
typedef vector<VLL> VVLL;

template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
template<class T>vector<T> split(const string& s){vector<T> v;istringstream is(s);T t;while(is>>t)v.PB(t);return v;}
//VS splitStr(const string& s, char delim='\0', bool keepEmpty=false){if(delim=='\0')return split<string>(s);VS v;istringstream is(s);string t;while(getline(is,t,delim))if(keepEmpty || t!="")v.PB(t);return v;}
VS splitStr(const string& s,const string& d="",bool keepEmpty=false){if(d.empty())return split<string>(s);VS v;string t;FOR(i,SZ(s))if(d.find(s[i])!=string::npos){if(keepEmpty||!t.empty()){v.PB(t);t="";}}else t+=s[i];if(!t.empty())v.PB(t);return v;}

int main()
{
	std::ios::sync_with_stdio(false);
    //cin.tie(NULL);
    vector<ll> A;A.reserve(23000);
    ll high = 1000000000;
    for(ll i=2;;++i)if((i*i)%2==1)
    {
        ll a = i;
        ll b = (a*a-1)/2;
        ll c = a*a-b;
        if (c<=high)
        {
            if(c*c != a*a + b*b)cout<<"Error: ";
            A.EB(c);
            //cout<<"("<<a<<","<<b<<","<<c<<")\n";
        }
        else break;
    }
    //cout<<"Size(A)="<<SZ(A)<<"\n";
    sort(ALL(A));
    ll T,N;
    cin>>T;
    while(T--)
    {
        cin>>N;
        auto it = upper_bound(ALL(A), N);
        ll count = it - A.begin();
        cout<<count<<"\n";
    }
    return 0;
}