#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int maxlen = 0;

struct BigInt {
  static const long long BASE = 100'000'000;
  static const int BASELEN = 8;

  vector<long long> digits;
  bool sign; // true: >= 0

  BigInt(long long x = 0) {
    if (x < 0) {
      sign = false;
      x *= -1;
    } else {
      sign = true;
    }
    while (x) {
      digits.emplace_back(x % BASE);
      x /= BASE;
    }
  }
  BigInt(string s) {
    sign = true;
    reverse(s.begin(), s.end());
    if (s.back() == '-') {
      sign = false;
      s.pop_back();
    }
    for (int i = 0; i < s.size(); i += BASELEN) {
      long long cur = 0;
      long long ten_pw = 1;
      for (int j = i; j < s.size() && j < i + BASELEN; ++j) {
        cur += ten_pw * (s[j] - '0');
        ten_pw *= 10;
      }
      digits.emplace_back(cur);
    }
  }

  explicit operator int() {
    int res = 0;
    for (int i = (int)digits.size() - 1; i >= 0; --i) {
        res = res * BASE + digits[i];
    }
    return res;
  }

  void fixup() {
      /// maxlen = max(maxlen, (int)digits.size());
    while (!digits.empty() && digits.back() == 0)
      digits.pop_back();
    if (digits.empty())
      sign = true;
  }
  BigInt(vector<long long> digits, bool sign): digits(digits), sign(sign) {
    fixup();
  }

  static bool compare_digits(vector<long long> left, vector<long long> right) {
    if (left.size() != right.size()) {
      return left.size() < right.size();
    }
    for (int i = int(left.size()) - 1; i >= 0; --i) {
      if (left[i] != right[i])
        return left[i] < right[i];
    }
    return false;
  }

  static vector<long long> add_digits(const vector<long long>& left, const vector<long long>& right) {
    vector<long long> ans(max(left.size(), right.size()) + 1);
    for (int i = 0; i < left.size(); ++i) {
      ans[i] += left[i];
    }
    for (int i = 0; i < right.size(); ++i) {
      ans[i] += right[i];
    }
    for (int i = 0; i + 1 < ans.size(); ++i) {
      if (ans[i] >= BASE) {
        ++ans[i + 1];
        ans[i] -= BASE;
      }
    }
    return ans;
  }

  // left >= right
  static vector<long long> sub_digits(const vector<long long>& left, const vector<long long>& right) {
    vector<long long> ans = left;
    for (int i = 0; i < right.size(); ++i)
      ans[i] -= right[i];
    for (int i = 0; i + 1 < left.size(); ++i) {
      if (ans[i] < 0) {
        ans[i] += BASE;
        --ans[i + 1];
      }
    }
    return ans;
  }

  void smart_add(const vector<long long>& other_digits, bool same_sign) {
    if (same_sign) {
      digits = add_digits(digits, other_digits);
    } else {
      if (compare_digits(digits, other_digits)) {
        sign ^= 1;
        digits = sub_digits(other_digits, digits);
      } else {
        digits = sub_digits(digits, other_digits);
      }
    }
    fixup();
  }

  BigInt& operator+=(const BigInt& other) {
    smart_add(other.digits, sign == other.sign);
    return *this;
  }

  BigInt& operator-=(const BigInt& other) {
    smart_add(other.digits, sign != other.sign);
    return *this;
  }

  bool operator==(const BigInt& other) const {
    return digits == other.digits && sign == other.sign;
  }

  bool operator<(const BigInt& other) const {
    if (sign && other.sign) {
      return compare_digits(digits, other.digits);
    } else if (sign) {
      return false;
    } else if (other.sign) {
      return true;
    } else {
      return compare_digits(other.digits, digits);
    }
  }

  BigInt& operator/=(long long x) {
    for (int i = int(digits.size()) - 1; i >= 0; --i) {
      long long r = digits[i] % x;
      digits[i] /= x;
      if (i)
        digits[i - 1] += r * BASE;
    }
    fixup();
    return *this;
  }

  bool is_zero() const {
    return digits.empty();
  }
};

BigInt operator+(const BigInt& a, const BigInt& b) {
  BigInt copy = a;
  copy += b;
  return copy;
}

BigInt operator-(const BigInt& a, const BigInt& b) {
  BigInt copy = a;
  copy -= b;
  return copy;
}

BigInt operator*(const BigInt& a, const BigInt& b) {
    /// maxlen = max((size_t)maxlen, a.digits.size() * b.digits.size());
  vector<long long> ans(a.digits.size() + b.digits.size());
  for (int i = 0; i < a.digits.size(); ++i) {
    for (int j = 0; j < b.digits.size(); ++j)
      ans[i + j] += a.digits[i] * b.digits[j];
  }
  for (int i = 0; i + 1 < ans.size(); ++i) {
    if (ans[i] >= BigInt::BASE) {
        long long d = ans[i] / BigInt::BASE;
      ans[i + 1] += d;
      ans[i] -= d * BigInt::BASE;
    }
  }
  return BigInt(ans, a.sign ^ b.sign ^ 1);
}

int get_len(long long x) {
  int ans = 0;
  while (x) {
    x /= 10;
    ++ans;
  }
  return ans;
}

ostream& operator<<(ostream& os, const BigInt& a) {
  if (!a.sign)
    os << '-';
  if (a.is_zero())
    os << 0;
  for (int i = 0; i < a.digits.size(); ++i) {
    long long cur = a.digits[a.digits.size() - i - 1];
    if (i != 0) {
      for (int j = 0; j < BigInt::BASELEN - get_len(cur); ++j)
        os << 0;
    }
    os << cur;
  }
  return os;
}

BigInt operator/(BigInt a, int b) {
    a /= b;
    return a;
}

BigInt get_P(BigInt n) {
    BigInt l = 1, r = n;
    while (BigInt(1) < r - l) {
        BigInt m = (l + r) / 2;
        if (n < m * (m + 1) / 2) {
            r = m;
        } else {
            l = m;
        }
    }
    return l;
}

const int SMALL = 100;
BigInt C[SMALL][SMALL];

const int MAXQ = 2e5;
BigInt Q[MAXQ];

vector<BigInt> expand(vector<BigInt> vals, int N) {
    int k = vals.size();
    for (int n = k; n < N; ++n) {
        vals.push_back(BigInt(0));
        for (int d = 1; d <= k; ++d) {
            if (d % 2 == 1) {
                vals[n] += vals[n - d] * C[k][d];
            } else {
                vals[n] -= vals[n - d] * C[k][d];
            }
        }
    }
    return vals;
}

vector<BigInt> convert(vector<BigInt> vals) {
    int k = vals.size();
    vector<BigInt> ans;
    for (int i = 0; i < k; ++i) {
        ans.push_back(vals[i]);
        BigInt d = vals[i];
        for (int j = i; j < k; ++j) {
            vals[j] -= d * C[j][i];
        }
    }
    return ans;
}

vector<BigInt> mulx(const vector<BigInt>& a) {
    vector<BigInt> res = expand(a, a.size() + 1);
    for (int i = 0; i < (int)res.size(); ++i) {
        res[i] = res[i] * i;
    }
    return res;
}

vector<BigInt> integ(const vector<BigInt>& a) {
    vector<BigInt> b(a.size() + 1);
    b[0] = 0;
    for (int i = 0; i < (int)a.size(); ++i) {
        b[i + 1] = a[i] + b[i];
    }
    return b;
}

BigInt eval(const vector<BigInt>& a, BigInt n) {
    BigInt res = 0;
    BigInt c = 1;
    for (int i = 0; i < (int)a.size(); ++i) {
        res += a[i] * c;
        c = c * (n - i);
        c /= (i + 1);
    }
    return res;
}

vector<BigInt> compose(const vector<BigInt>& a, const vector<BigInt>& b, const vector<BigInt>& ca) {
    int sz = (a.size() - 1) * (b.size() - 1) + 1;
    vector<BigInt> res(sz);
    vector<BigInt> valb = expand(b, sz);
    /// vector<BigInt> ca = convert(a);
    for (int i = 0; i < sz; ++i) {
        res[i] = eval(ca, valb[i]);
    }
    return res;
}

vector<BigInt> operator+(vector<BigInt> a, vector<BigInt> b) {
    int sz = max(a.size(), b.size());
    a = expand(a, sz);
    b = expand(b, sz);
    for (int i = 0; i < (int)a.size(); ++i) {
        a[i] += b[i];
    }
    return a;
}

vector<BigInt> operator-(vector<BigInt> a, vector<BigInt> b) {
    int sz = max(a.size(), b.size());
    a = expand(a, sz);
    b = expand(b, sz);
    for (int i = 0; i < (int)a.size(); ++i) {
        a[i] -= b[i];
    }
    return a;
}

vector<BigInt> operator*(vector<BigInt> a, vector<BigInt> b) {
    int sz = a.size() + b.size() - 1;
    a = expand(a, sz);
    b = expand(b, sz);
    for (int i = 0; i < sz; ++i) {
        a[i] = a[i] * b[i];
    }
    return a;
}

const int MAXTIER = 3;

vector<BigInt> tier[MAXTIER];
vector<BigInt> cStier[MAXTIER];
vector<BigInt> cStierx[MAXTIER];
BigInt pref[MAXTIER][MAXQ];

void ensure(vector<BigInt>& a, int n) {
    while (n >= (int)a.size()) {
        a.push_back(0);
    }
}

BigInt get_Q_bfs(BigInt n) {
    BigInt ans = 0;
    BigInt k = 1;
    BigInt cur_n = n;
    vector<BigInt> coeff;
    while (!coeff.empty() || !(k == 0)) {
        /// maxlen = max(maxlen, (int)coeff.size());
        /// cerr << k << " " << coeff.size() << " " << cur_n << endl;
        BigInt k1 = 0;
        vector<BigInt> coeff1 = {};
        BigInt n1 = get_P(cur_n);
        if (!(k == BigInt(0))) {
            BigInt n = cur_n;
            if (n < BigInt(MAXQ)) {
                ans += Q[int(n)] * k;
            } else {
                k1 -= ((n1 + 2) * (n1 + 1) / 2 - 1 - n) * k;
                ensure(coeff1, 0);
                coeff1[0] += k;
                /// vector<BigInt> cur = {k, k + k};
                /// vals1 = vals1 + cur;
            }
        }
        if (!coeff.empty()) {
            BigInt N = cur_n;
            if (N < MAXQ) {
                /**vals = expand(vals, int(N) + 1);
                for (int i = 1; i <= int(N); ++i) {
                    ans += vals[i] * Q[i];
                }*/
                for (int i = 0; i < (int)coeff.size(); ++i) {
                    ans += coeff[i] * pref[i][int(N)];
                }
            } else {
                for (int i = 0; i < (int)coeff.size(); ++i) {
                    BigInt cSfN = eval(cStier[i], N + 1);
                    BigInt k = eval(cStierx[i], (n1 + 1) * (n1 + 2) / 2) - eval(cStierx[i], N + 1);
                    k -= (n1 * (n1 + 1) / 2 + n1) * (eval(cStier[i], (n1 + 1) * (n1 + 2) / 2) - cSfN);
                    k1 -= k * coeff[i];
                    ensure(coeff1, i + 1);
                    coeff1[0] += cSfN * coeff[i];
                    coeff1[i + 1] += coeff[i];
                }
                /**vector<BigInt> Sf = integ(vals);
                vector<BigInt> Sfx = integ(mulx(vals));
                vector<BigInt> cSf = convert(Sf), cSfx = convert(Sfx);

                BigInt cSfN = eval(cSf, N + 1);
                BigInt k = eval(cSfx, (n1 + 1) * (n1 + 2) / 2) - eval(cSfx, N + 1);
                k -= (n1 * (n1 + 1) / 2 + n1) * (eval(cSf, (n1 + 1) * (n1 + 2) / 2) - cSfN);
                vector<BigInt> compSf = compose(Sf, {BigInt(0), BigInt(1), BigInt(3)}, cSf);
                vector<BigInt> compSf1 = expand(compSf, compSf.size() + 1);
                for (int i = 0; i < (int)compSf.size(); ++i) {
                    compSf1[i] = compSf1[i + 1];
                }
                compSf1.pop_back();
                vector<BigInt> compSfx = compose(Sfx, {BigInt(0), BigInt(1), BigInt(3)}, cSfx);
                vector<BigInt> compSfx1 = expand(compSfx, compSfx.size() + 1);
                for (int i = 0; i < (int)compSfx.size(); ++i) {
                    compSfx1[i] = compSfx1[i + 1];
                }
                compSfx1.pop_back();

                vector<BigInt> f = {cSfN};
                f = f - compSf1;
                f = f + mulx(f);
                f = f + compSfx1 - compSfx;
                vector<BigInt> sb = compSf1 - compSf;
                vector<BigInt> mlt = {BigInt(-1), BigInt(0), BigInt(2)};
                f = f - sb * mlt;
                vals1 = vals1 + f;
                k1 -= k;*/
            }
        }
        cur_n = n1;
        coeff = move(coeff1);
        k = k1;
    }
    return ans;
}

/// BigInt crutch = 0;

void solve() {
    string sn = "10000000000000000000000000000000000000000";
    cin >> sn;
    BigInt n(sn);

    /// crutch += get_Q_bfs(n);
    cout << get_Q_bfs(n) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  auto start = clock();

  for (int n = 0; n < SMALL; ++n) {
    C[n][0] = 1;
    for (int k = 1; k <= n; ++k) {
        C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
    }
  }

  /// cerr << (clock() - start) * 1.0 / CLOCKS_PER_SEC << endl;

  Q[1] = 1;
  int j = 1;
  for (int i = 2; i < MAXQ; ++i) {
    if ((j + 1) * (j + 2) / 2 == i) ++j;
    Q[i] = Q[i - 1] + Q[j];
  }

  tier[0] = {BigInt(1), BigInt(2)};
  for (int i = 1; i < MAXTIER; ++i) {
    vector<BigInt> vals = tier[i - 1];
    vector<BigInt> Sf = integ(vals);
    vector<BigInt> Sfx = integ(mulx(vals));
    vector<BigInt> cSf = convert(Sf), cSfx = convert(Sfx);

    vector<BigInt> compSf = compose(Sf, {BigInt(0), BigInt(1), BigInt(3)}, cSf);
    vector<BigInt> compSf1 = expand(compSf, compSf.size() + 1);
    for (int i = 0; i < (int)compSf.size(); ++i) {
        compSf1[i] = compSf1[i + 1];
    }
    compSf1.pop_back();
    vector<BigInt> compSfx = compose(Sfx, {BigInt(0), BigInt(1), BigInt(3)}, cSfx);
    vector<BigInt> compSfx1 = expand(compSfx, compSfx.size() + 1);
    for (int i = 0; i < (int)compSfx.size(); ++i) {
        compSfx1[i] = compSfx1[i + 1];
    }
    compSfx1.pop_back();

    vector<BigInt> f = {};
    f = f - compSf1;
    f = f + mulx(f);
    f = f + compSfx1 - compSfx;
    vector<BigInt> sb = compSf1 - compSf;
    vector<BigInt> mlt = {BigInt(-1), BigInt(0), BigInt(2)};
    f = f - sb * mlt;
    tier[i] = f;
  }
  /// cerr << "tiers found" << endl;
  for (int i = 0; i < MAXTIER; ++i) {
    cStier[i] = convert(integ(tier[i]));
    cStierx[i] = convert(integ(mulx(tier[i])));
    pref[i][0] = 0;
    auto res = expand(tier[i], MAXQ);
    /// cerr << i << endl;
    for (int n = 1; n < MAXQ; ++n) {
        pref[i][n] = pref[i][n - 1] + Q[n] * res[n];
    }
  }

  /// cerr << (clock() - start) * 1.0 / CLOCKS_PER_SEC << endl;

  int tst = 1;
  cin >> tst;
  while (tst--) {
    solve();
    /// cout.flush();
  }
  /// cerr << maxlen << endl;
  return 0;
}