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 C continue;
#define R return

#define int long long
#define D double
#define I insert
#define ull unsigned long long
#define ui unsigned int
#define ld long double

#define pb emplace_back
#define pf push_front
#define F first
#define S second
#define mp make_pair

#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vb vector<bool>
#define vd vector<D>
#define vull vector<ull>
#define vld vector<ld>
#define vpld vector<pld>
#define vpii vector<pii>
#define vpDD vector<pDD>

#define all(v) v.begin(), v.end()
#define allcomp(v) v.begin(), v.end(), comp

#define pii pair<int, int>
#define pld pair<ld, ld>
#define pDD pair<D, D>

#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type, vector<type>, greater<type>>

#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define mis map<int, string>
#define mib map<int, bool>
#define mcb map<char, bool>

#define umii unordered_map<int, int>
#define umib unordered_map<int, bool>
#define umci unordered_map<char, int>
#define umsi unordered_map<string, int>
#define umis unordered_map<int, string>

#define init(arr, val) memset(arr, val, sizeof(arr))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define distance(a, b, p, q) sqrt((p - a) * (p - a) + (q - b) * (q - b))

#define pp(n) printf("%.10Lf", n);
#define nl "\n"
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);

string vow = "aeiou";
int month[] = { -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = { -2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

const int dx4[] = { -1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = { -1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[] = { -1, 0, 1, -1, 1, -1, 0, 1};
const ld pie = 3.1415926535897932384626;
const int special_prime = 982451653l; // The 50,000,000th prime number
const int mod = 1e9 + 7;

#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b )
///DEBUGGER
void __print(int x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif
//VECTOR
template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
    for (auto &i : a)
        cin >> i;
    return in;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &a)
{
    for (auto &i : a)
        cout << i << " ";
    return out;
}
//MAP
template <class T, class U>
ostream &operator<<(ostream &out, const map<T, U> &a)
{
    for (auto &i : a)
        cout << "(" << i.first << ", " << i.second << ")\n";
    return out;
}
template <class T, class U>
ostream &operator<<(ostream &out, const unordered_map<T, U> &a)
{
    for (auto &i : a)
        cout << "(" << i.first << ", " << i.second << ")\n";
    return out;
}
bool comp(int a, int b)
{
    return a > b;
}

void sieve(vi &prime)
{
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= 99999; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= 99999; i += p)
                prime[i] = false;
        }
    }
}
/*                      CODE STARTS FROM HERE                     */

void solve()
{
    int n; cin >> n;
    int ans = 0;
    int k = 3;
    int d = k * k + 1;
    while (d <= 2 * n)
    {
        ans++;
        k += 2;
        d = k * k + 1;
    }
    cout << ans << nl;
}
int32_t main()
{
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #
    fast

    int t = 1;

    cin >> t;
    // cin>>ws;
    //vi prime(99999, true);
    //sieve(prime);

    for (int i = 1; i <= t; i++)
        solve();
}