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 ll long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define pob pop_back
#define MP make_pair
#define MT make_tuple
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rept(it,v) for(auto it=v.begin();it!=v.end();it++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define endl "\n"
#define ct continue
#define ub upper_bound
#define fill(a,b) memset(a,b,sizeof(a))
#define lb lower_bound
#define bs binary_search
#define pll pair<ll,ll> 
#define pii pair<int,int>
#define vll vector<ll>
#define vii vector<int>
#define deb(x)  cout<<#x<<" : "<<x<<endl

//Ordered Set-
//#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> 

const ll  mod=1e9+7;

ll bin(ll a, ll b)
{
	if(b==0)
	return 1;
	if(b&1)
		return (a*bin((a*a)%mod,b/2))%mod;
	return (1*bin((a*a)%mod,b/2))%mod;
}

vector<ll>v;

void I_m_Beast()
{	
	ll n,a;
	cin>>n;
	if(n<=3)
		cout<<"0\n";
	else
	{
		ll sum=n+n-1;
		int idx=upper_bound(v.begin(),v.end(),sum)-v.begin();
		cout<<idx<<endl;
	}
}

int main()
{	
	fastio;
	int t=1;
	cin>>t;
	ll x=3;
	while(x*x<=5000000000)
	{
		v.pb(x*x);
		x+=2;
	}
	while(t--)
	{
		I_m_Beast();
	}	
	return 0;	
}