#!/usr/bin/env python3

import math
from fractions import Fraction

def add(p, q):
	res = [0] * max(len(p), len(q))
	for i in range(len(p)):
		res[i] += p[i]
	for i in range(len(q)):
		res[i] += q[i]
	return res

def sub(p, q):
	res = [0] * max(len(p), len(q))
	for i in range(len(p)):
		res[i] += p[i]
	for i in range(len(q)):
		res[i] -= q[i]
	return res

def mult(p, q):
	res = [0] * ((len(p) - 1) + (len(q) - 1) + 1)
	for i in range(len(p)):
		for j in range(len(q)):
			res[i + j] += p[i] * q[j]
	return res

def subst(p, q):
	# P(Q(x))
	res = [0]
	cur = [1]
	for c in p:
		res = add(res, [x * c for x in cur])
		cur = mult(cur, q)
	return res

def apply_poly(p, x):
	res = 0
	for c in p[::-1]:
		res = res * x + c
	return res

def norm_to_bin(p):
	res = [0] * len(p)
	bins = [[1]]
	for i in range(len(p) - 1):
		q = mult(bins[-1], [i, 1])
		bins.append(q)
	for i in range(len(p) - 1, -1, -1):
		c = p[i]
		res[i] = c
		p = add(p, [-c * x for x in bins[i]])
	return res

def lift(p):
	p = [0] + p
	for i in range(1, len(p)):
		p[i] = Fraction(p[i]) / i
	return p

def bin_to_norm(p):
	res = [0]
	q = [1]
	for i in range(len(p)):
		res = add(res, [x * p[i] for x in q])
		q = mult(q, [i, 1])
	return res

def _poly_to_sum(p):
	return bin_to_norm(lift(norm_to_bin(p)))

# N = 3_000
# D = 37

N = 184_000
D = 17
pss = [_poly_to_sum([0] * i + [1]) for i in range(D)]

def poly_to_sum(p):
	res = [0]
	for i in range(len(p)):
		res = add(res, [x * p[i] for x in pss[i]])
	return res

def sumpoly(p, x):
	return apply_poly(poly_to_sum(p), x)

def varsumpoly(p, q):
	return subst(poly_to_sum(p), q)


def isqrt(n: int) -> int: # pylint: disable=too-many-branches
    # pylint: disable=line-too-long # Accommodate long link URLs on docstring.
    """
    Returns the largest root such that ``root**2 <= n (root + 1)**2 > n``.
    When using Python 3.8 or later, this function acts as a wrapper for the
    built-in :obj:`math.isqrt` function.
    For all other supported versions of Python, this function reverts to a
    pure Python algorithm that is adapted from an
    `implementation by Alexander Gosselin <https://gist.github.com/castle-bravo/e841684d6bad8e0598e31862a7afcfc7>`__,
    which is based on a `Stack Overflow answer by Tobin Fricke <http://stackoverflow.com/a/23279113/2738025>`__.
    >>> isqrt(4)
    2
    >>> isqrt(16)
    4
    >>> list(map(isqrt, range(16, 26)))
    [4, 4, 4, 4, 4, 4, 4, 4, 4, 5]
    >>> from random import randint
    >>> all([isqrt(r**2 + randint(0, r)) == r  for r in range(0, 1000)])
    True
    >>> r = randint(2**511, 2**512 - 1)
    >>> isqrt(r**2) == r
    True
    >>> isqrt(2**30000) == 2**15000
    True
    The type and sign of the input are checked.
    >>> isqrt(-2)
    Traceback (most recent call last):
      ...
    ValueError: input must be a non-negative integer
    >>> isqrt('abc')
    Traceback (most recent call last):
      ...
    TypeError: input must be an integer
    Test scenarios in which the :obj:`math.isqrt` function is not available.
    >>> if hasattr(math, 'isqrt'):
    ...     delattr(math, 'isqrt')
    >>> isqrt(16)
    4
    >>> isqrt(2**30000) == 2**15000
    True
    >>> isqrt(-2)
    Traceback (most recent call last):
      ...
    ValueError: input must be a non-negative integer
    >>> isqrt('abc')
    Traceback (most recent call last):
      ...
    TypeError: input must be an integer
    """
    # Try using built-in integer square root function (available in Python 3.8 or later).
    # To ensure this implementation is backwards-compatible with previous versions while
    # not introducing performance overheads for the most common case, only convert
    # exceptions if the initial call to the built-in function raises an exception.
    if hasattr(math, 'isqrt'):
        try:
            return math.isqrt(n)
        except ValueError as e:
            if str(e) == 'isqrt() argument must be nonnegative':
                raise ValueError('input must be a non-negative integer') from None
            # Continue to default implementation to ensure backwards-compatible behavior.
        except TypeError as e:
            if str(e).endswith('object cannot be interpreted as an integer'):
                raise TypeError('input must be an integer') from None
            # Continue to default implementation to ensure backwards-compatible behavior.
        except: # pylint: disable=bare-except # pragma: no cover
            pass # Continue to default implementation to ensure backwards-compatible behavior.

    try: # Attempt to use the :obj:`math.sqrt` function.
        root = int(math.sqrt(n))
        if root * root == n: # No error from floating point conversion.
            return root
    except ValueError as e:
        if str(e) == 'math domain error':
            raise ValueError('input must be a non-negative integer') from None
        # Continue to default implementation to ensure backwards-compatible behavior.
    except TypeError as e:
        if str(e).startswith('must be real number'):
            raise TypeError('input must be an integer') from None
        # Continue to default implementation to ensure backwards-compatible behavior.
    except OverflowError:
        pass # Use the integer-only bit-wise algorithm.

    if n is None or (not isinstance(n, int)):
        raise TypeError('input must be an integer') # pragma: no cover

    if n < 0:
        raise ValueError('input must be a non-negative integer') # pragma: no cover

    root = 0 # Running result.
    rmdr = 0 # Running remainder n - root**2.
    for s in reversed(range(0, n.bit_length(), 2)): # Shift n by s bits.
        bits = n >> s & 3 # The next two most significant bits of n.
        rmdr = rmdr << 2 | bits # Increase the remainder.
        cand = root << 2 | 1 # Shifted candidate root value to try.
        bit_next = int(rmdr >= cand) # The next bit in the remainder.
        root = root << 1 | bit_next # Add next bit to running result.
        rmdr -= cand * bit_next # Reduce the remainder if bit was added.
    return root

def S(n):
	return (n + 1) * (n + 2) // 2 - 1

def P(n):
	# max k: (k + 1) * (k + 2) / 2 - 1 >= n
	# max k: (k + 1) * (k + 2) >= 2 * n + 2
	# max k: k^2 + 3k >= 2 * n
	# max k: 4k^2 + 12k >= 8 * n
	# max k: 4k^2 + 12k + 9 >= 8 * n + 9
	k = (isqrt(8 * n + 9) - 3) // 2
	while S(k) < n:
		k += 1
	return k

Q = [1] * N
prefQ = [[1] * N for i in range(D)]

for i in range(2, N):
	Q[i] = Q[i - 1] + Q[P(i)]
	cur = Q[i]
	for j in range(D):
		prefQ[j][i] = prefQ[j][i - 1] + cur
		cur *= i

denom = 107520
for v in pss:
	for i in range(len(v)):
		if isinstance(v[i], Fraction) and denom % v[i].denominator == 0:
			v[i] = int(v[i] * denom)
		else:
			v[i] *= denom

def f(n, p):
	global find_Q
	# returns sum for k = 1 .. n of Q(k) * p(k)
	if n < N:
		return sum(prefQ[i][n] * p[i] for i in range(len(p)))
	
	mx = P(n)
	fr = S(mx - 1) + 1

	p = poly_to_sum(p)
	q = [-x for x in subst(p, [-1, 1])]
	q[0] += apply_poly(p, n)
	q = poly_to_sum(q)

	# ans += sum_{fr <= i <= n} (sumpoly(p, n) - sumpoly(p, i - 1))
	ans = find_Q(mx) * (apply_poly(q, n) - apply_poly(q, fr - 1))

	# ans += sum_{j < mx} sum_{S(j - 1) < i <= S(j)} (sumpoly(p, n) - sumpoly(p, i - 1))
	mult = 2 ** (len(q) - 1)
	ans *= mult
	for i in range(len(q)):
		q[i] *= 2 ** (len(q) - 1 - i)
	# q = sub(subst(q, [0, Fraction(3, 2), Fraction(1, 2)]), subst(q, [-1, Fraction(1, 2), Fraction(1, 2)]))
	q = sub(subst(q, [0, 3, 1]), subst(q, [-2, 1, 1]))
	ans += f(mx - 1, q)

	return ans // (denom**2 * mult)


def find_Q(n):
	if n < N:
		return Q[n]

	mx = P(n)
	return f(mx, [1, 1]) - find_Q(mx) * (S(mx) - n)

if __name__ == "__main__":
	t = int(input())
	for _ in range(t):
		n = int(input())
		# n = 10**40
		print(find_Q(n))