from math import isqrt

# ======== 预处理：多项式 f 和 F 的点值表示 ========

# 多项式最大次数
MAX_K = 30

# prod[i][j] = product(i - k), 0 <= k <= j, k != i
prod = []
for i in range(MAX_K + 1):
    prod.append([])
    p = 1
    for j in range(MAX_K + 1):
        if i != j:
            p *= i - j
        prod[-1].append(p)

# 给 k 次多项式的点值表示 (0, y[0]), (1, y[1]), ..., (k, y[k])
# 利用拉格朗日插值法，求自变量为 x 时多项式的值
def eval(x, y):
    if x >= 0 and x < len(y):
        return y[x]

    p = 1
    for i in range(len(y)):
        p *= x - i

    nume, deno = 0, 1
    for i in range(len(y)):
        a = y[i] * (p // (x - i))
        b = prod[i][len(y) - 1]
        nume = nume * b + deno * a
        deno *= b
    return nume // deno

# 最大递归深度
MAX_DEP = 4

# polys[i] 是 f^{(i)}(x) 的点值表示
polys = []
polys.append([1])
# smPolys[i] 是 F^{(i)}(x) 的点值表示
smPolys = []

for _ in range(MAX_DEP):
    prevLen = len(polys[-1])

    # F^{(i)}(x) 是 f^{(i)}(x) 的前缀和
    sm = [0]
    for y in polys[-1][1:]:
        sm.append(sm[-1] + y)
    sm.append(sm[-1] + eval(prevLen, polys[-1]))
    smPolys.append(sm)

    # f^{(i + 1)}(x) = F^{(i)}(x * (x + 1) // 2 - 1)
    sq = []
    for x in range(0, prevLen * 2 + 1):
        sq.append(eval(x * (x + 1) // 2 - 1, sm))
    polys.append(sq)

# ======== 预处理：P 和 Q 小范围的值 ========

# 最大递归深度时，n < MAX_LEN
MAX_LEN = 610

P = [0]
t = 1
while len(P) <= MAX_LEN:
    for _ in range(t + 1):
        P.append(t)
    t += 1

Q = [0, 1]
for i in range(2, MAX_LEN):
    Q.append(Q[-1] + Q[P[i]])

# ======== 预处理：g(d, n) 在 d <= MAX_DEP，n < MAX_LEN 时的值 ========

# S[d][n] = g(d, n)
S = []
for i in range(MAX_DEP + 1):
    S.append([0])
    for j in range(1, MAX_LEN):
        S[-1].append(S[-1][-1] + eval(j, polys[i]) * Q[P[j]])

# ======== 正式计算 ========

# 若 P(n) = p，则 (p + 3) * p // 2 >= n 且 p 最小
# 通过解二次方程算出来，因为开根号和除法都下取整了，要往后检查几个数
def calcP(n):
    p = (isqrt(8 * n + 9) - 3) // 2
    while p * (p + 3) // 2 < n:
        p += 1
    return p

def g(d, n):
    if n < MAX_LEN:
        return S[d][n]
    np = calcP(n)
    return eval(n, smPolys[d]) * g(0, np) - g(d + 1, np)

T = int(input())
for _ in range(T):
    n = int(input())
    print(g(0, n))