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 double      ld;
typedef long long int    ll;
typedef pair<ll, ll>     pl;
typedef vector<ll>       vl;
typedef vector<pl>       vpl;
typedef vector<vl>       vll;
#define endl             '\n'
#define F                first
#define S                second
#define MAX              90000000
#define mk               make_pair
#define pb               push_back
#define p1(a)            cout << a << endl;
#define all(x)           x.begin() , x.end()
#define no               cout << "NO" << endl;
#define yes              cout << "YES" << endl;
#define PI               3.1415926535897932384626
#define p2(a,b)          cout << a << " " << b << endl;
#define p3(a,b,c)        cout << a << " " << b << " " << c << endl;
#define scan(a,n)        for (ll i = 0; i < n; i++) {cout << a[i];}
#define print(a)         for (auto x : a )cout << x << " "; cout << endl;
#define fast             ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
ll mod = 1e9 + 7;
ll inf = 1e9 + 7;
vl v;
void xxx()
{
    ll n = 1e12 + 12;
    ll i;
    for (i = 1; i <= sqrt(n); i++)
    {
        ll a = i;
        ll b = ((a * a) - 1) / 2;
        ll c = b + 1;
        if ((a * a) + (b * b) == (c * c) && (c == (a * a) - b) && a <= b && b <= c)
            v.pb(c);
    }
    // print(v)
}
void solve()
{
    ll n;
    cin >> n;

    ll x = upper_bound(v.begin(), v.end(), n) - v.begin();

    cout << x << endl;

}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    fast;
    xxx();
    ll t = 1;
    cin >> t;

    while (t--)
    {
        // cout << "Case #" << i + 1 << ": ";
        solve();
    }
}

/*
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
*/