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:
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Code written by Aditya ;)   ||  Codechef/codeforces: @adityaraj5200 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#include<bits/stdc++.h>

using namespace std;

#define fastio                        \
     ios_base::sync_with_stdio(false);   \
     cin.tie(NULL);                      \
     cout.tie(NULL)
#define endl                  "\n" 
#define mod                   1000000007
#define PI                    3.14159265358979323846
#define deb(x)                cout<<'>'<<#x<<" = "<<x<<endl
#define deb2(x, y)            cout<<'>'<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<endl
#define all(x)                x.begin(), x.end()
#define sortall(x)            sort(all(x))
#define lcm(a,b)              (a*b)/__gcd(a,b)
#define range(a,b)            (abs(b-a)+1)
#define gap(a,b)              (abs(b-a)-1)
#define pb                    push_back
#define mp                    make_pair
#define lb                    lower_bound
#define ub                    upper_bound
#define ctoi(ch)              ch-'0' 
#define yes                   "YES"
#define no                    "NO"
#define inf                   INT_MAX
#define ninf                  INT_MIN

typedef long long             ll;
typedef unsigned long long    ull;
typedef long double           ld;
typedef vector<int>           vi;
typedef vector<vi>            vvi;
typedef vector<long long>     vll;
typedef pair<int,int>         pii;
typedef vector<pii>           vpii;
typedef vector<bool>          vb;
typedef vector<vb>            vvb;
typedef vector<string>        vs;
typedef vector<vpii>          vvpii;
int vec_val;

/*/------------------------------ CODE BEGINS ------------------------------/*/

ll solve(){
     int n;
     cin>>n;
     ll ans = 0;
     // Pythagoras theorem fulfills on : 
     // cout<<"Pythagoras theorem fulfills on : "<<endl;
     // for(int a=1;a<=n;a++){
     //      for(int b=1;b<=n;b++){ 
     //           for(int c=1;c<=n;c++){
     //                if(c*c == a*a + b*b)
     //                cout<<c<<' '<<a<<' '<<b<<' '<<endl;
     //           }
     //      }
     // }

     // Originating cases when req. condition happens
     // cout<<"Originating cases when req. condition happens: "<<endl;
     // int count = 0;
     // for(int a=1;a<=n;a++){
     //      for(int b=1;b<=n;b++){
     //           for(int c=1;c<=n;c++){
     //                if(c*c == a*a + b*b)
     //                if(c == a*a - b)
     //                count++;
     //           }
     //      }
     // }
     // return count;
     
     /* For n=1000, answer is 21 */

     ll val = 0;
     ll a = 3;
     while(1){
          val = (ll(a*a)+1)/2;
          if(val<=n) ans++;
          else break;

          a += 2;
     }
     return ans;
}
/*/------------------------------- CODE ENDS -------------------------------/*/

int main(){
     fastio;
     // cout << setprecision(12) << fixed;
     int tc=1;
     cin>>tc;
     for(int t=1;t<=tc;t++){
          // cout<<endl<<"Case #" << t  << ": "<<endl;
          cout<<solve();
          cout<<endl;
     }
     return 0;
}