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 PYTHON3):

Solution:
from collections import defaultdict,OrderedDict,Counter
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
# import numpy as np
from queue import Queue,PriorityQueue
from heapq import heapify,heappop,heappush
from statistics import median,mean
from math import gcd,sqrt,floor,factorial,ceil,log2,log10,log
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10**8)
import math
import os
import bisect
import collections
mod=pow(10,9)+7
import random
from random import random,randint,randrange
from time import  time;
def ncr(n, r, p=mod):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
            p - 2, p)) % p
def normalncr(n,r):
    r=min(r,n-r)
    count=1;
    for i in range(n-r,n+1):
        count*=i;

    for i in range(1,r+1):
        count//=i;
    return count

inf=float("inf")
adj=defaultdict(set)
visited=defaultdict(int)
def addedge(a,b):
    adj[a].add(b)
    adj[b].add(a)
def bfs(v):
    q=Queue()
    q.put(v)
    visited[v]=1
    while q.qsize()>0:
        s=q.get_nowait()
        print(s)
        for i in adj[s]:
            if visited[i]==0:
                q.put(i)
                visited[i]=1
def dfs(v,visited):
    if visited[v]==1:
        return;
    visited[v]=1

    print(v)
    for i in adj[v]:
        dfs(i,visited)
# a9=pow(10,6)+10
# prime = [True for i in range(a9 + 1)]
# def SieveOfEratosthenes(n):
#     p = 2
#     while (p * p <= n):
#         if (prime[p] == True):
#             for i in range(p * p, n + 1, p):
#                 prime[i] = False
#         p += 1
# SieveOfEratosthenes(a9)
# prime_number=[]
# for i in range(2,a9):
#     if prime[i]:
#         prime_number.append(i)
def reverse_bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid+1
    return lo
def reverse_bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x >= a[mid]:
            hi = mid
        else:
            lo = mid+1
    return lo

def get_list():
    return list(map(int,input().split()))
def get_str_list_in_int():
    return [int(i) for i in list(input())]
def get_str_list():
    return list(input())
def get_map():
    return map(int,input().split())
def input_int():
    return int(input())
def matrix(a,b):
    return [[0 for i in range(b)] for j in range(a)]
def swap(a,b):
    return b,a
def find_gcd(l):
    a=l[0]
    for i in range(len(l)):
        a=gcd(a,l[i])
    return a;
def is_prime(n):
    sqrta=int(sqrt(n))
    for i in range(2,sqrta+1):
        if n%i==0:
            return 0;
    return 1;
def prime_factors(n):
    sqrta = int(sqrt(n))
    for i in range(2,sqrta+1):
        if n%i==0:
            return [i]+prime_factors(n//i)
    return [n]

nc="NO"
yc="YES"
ns="No"
ys="Yes"

# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
# input=stdin.readline
# print=stdout.write
def get_next(a):
    if a==n:
        return 1;
    return a+1;
def get_prev(a):
    if a==1:
        return n;
    return a-1;
def div(a,n):
    return a//(n//2)
def mod(k,n):
    k=k%n;
    if k==0:
        return n;
    return k;
# n=1000000000
# for i in range(1,1000000,2):
#         sq=i*i;
#         b=(sq-1)//2;
#         a=i;
#         c=b+1;
#         if c>n:
#             break;
#         if a<=b<=c<=n:
#             print(a,b,c)
# l=[0 for i in range(pow(10,5))]
# count=0
# for i in range(1,1000000):
#     if i%2==0:
#         l.append(l[-1])
#         continue
#     sq=i*i;
#     b=(sq-1)//2;
#     a=i;
#     c=b+1;
#     if c>n:
#         break;
#     if 1<=a<=b<=c<=n:
#         l[c]+=1

t=int(input())
for i in range(t):
    n=int(input())
    a=int(sqrt(2*n-1))
    if a%2==0:
        a-=1;
    print((a-1)//2)