#!/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):
	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 * 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 * N + i] = prefQ[j * N + 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 + 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))