from math import isqrt

K = 100000

C = [[0] * 100 for _ in range(100)]
C[0][0] = 1
for i in range(99):
    for j in range(99):
        C[i + 1][j] += C[i][j]
        C[i + 1][j + 1] += C[i][j]


P = []
for x in range(K):
    P += [x] * (x + 1)
    if len(P) >= K:
        break

Q = [0] * K
Q[1] = 1
for n in range(2, K):
    Q[n] = Q[n - 1] + Q[P[n]]


def lagrange_interpolate_iota(f, x):
    n = len(f)
    f = f.copy()
    a = [0] * n
    for i in range(n):
        a[i] = f[i]
        for j in range(i, n):
            f[j] -= a[i] * C[j][i]
    comb = 1
    res = 0
    for i in range(n):
        res += a[i] * comb
        comb = comb * (x - i) // (1 + i)
    return res


FF = []
FF.append([1])
AA = []

for i in range(5):
    f = FF[i]
    g = [0] + f
    for i in range(1, len(g)):
        g[i] += g[i - 1]
    f = [lagrange_interpolate_iota(g, x * (x + 1) // 2)
         for x in range(2 * len(g) - 1)]
    FF.append(f)

for f in FF:
    g = [0] + f
    for i in range(1, len(g)):
        g[i] += g[i - 1]
    f = g
    n = len(f)
    a = [0] * n
    for i in range(n):
        a[i] = f[i]
        for j in range(i, n):
            f[j] -= a[i] * C[j][i]
    AA.append(a)


def newton(idx, x):
    a = AA[idx]
    comb = 1
    res = 0
    for i, v in enumerate(a):
        res += v * comb
        comb = comb * (x - i) // (1 + i)
    return res


def calc_sum(f_idx, n):
    # sum_{i=0}^n f(i)Q(i)
    f = FF[f_idx]
    if n < len(f):
        res = 0
        for i in range(n + 1):
            res += f[i] * Q[P[i]]
        return res
    ANS = 0
    ANS += newton(f_idx, n + 1) * calc_Q(calc_P(n))
    k = isqrt(8 * n + 1)
    k = (k - 1) // 2
    ANS -= calc_sum(f_idx + 1, k)
    return ANS


def calc_P(n):
    k = isqrt(8 * n + 1)
    return (k - 1) // 2


def calc_Q(n):
    if n < K:
        return Q[n]
    return calc_sum(0, n)


T = int(input())
for _ in range(T):
    N = int(input())
    print(calc_Q(N))