#include <bits/stdc++.h>
using namespace std;

namespace decimal {
class bigint {
public:
  static const int BASE = 1000000000;
  static const long long BASE2 = (long long)BASE * BASE;

  bigint();
  bigint(const string &s);
  bigint(const char *s);
  bigint(int x);
  bigint(long long x);
  bigint(const bigint &b);
  bigint(const vector<int> &digits, bool is_negative = false);

  bool is_zero() const;
  string to_string() const;
  int to_int() const;
  long long to_long_long() const;
  int compare_with(const bigint &b) const;
  int compare_with(int x) const;
  int compare_with(long long x) const;

  bigint &operator=(const string &s);
  bigint &operator=(const char *s);
  bigint &operator=(int x);
  bigint &operator=(long long x);
  bigint &operator=(const bigint &b);

  friend bigint operator+(const bigint &a, const bigint &b);
  friend bigint operator+(const bigint &a, int x);
  friend bigint operator+(int x, const bigint &a);
  friend bigint operator+(const bigint &a, long long x);
  friend bigint operator+(long long x, const bigint &a);

  friend bigint operator-(const bigint &a, const bigint &b);
  friend bigint operator-(const bigint &a, int x);
  friend bigint operator-(int x, const bigint &a);
  friend bigint operator-(const bigint &a, long long x);
  friend bigint operator-(long long x, const bigint &a);

  friend bigint operator*(const bigint &a, const bigint &b);
  friend bigint operator*(const bigint &a, int x);
  friend bigint operator*(int x, const bigint &a);

  friend bigint operator/(const bigint &a, const bigint &b);
  friend bigint operator/(const bigint &a, int x);

  friend bigint operator%(const bigint &a, const bigint &b);
  friend bigint operator%(const bigint &a, int x);

  friend bool operator<(const bigint &a, const bigint &b);
  friend bool operator<(const bigint &a, int x);
  friend bool operator<(int x, const bigint &b);
  friend bool operator<(const bigint &a, long long x);
  friend bool operator<(long long x, const bigint &b);

  friend bool operator>(const bigint &a, const bigint &b);
  friend bool operator>(const bigint &a, int x);
  friend bool operator>(int x, const bigint &b);
  friend bool operator>(const bigint &a, long long x);
  friend bool operator>(long long x, const bigint &b);

  friend bool operator<=(const bigint &a, const bigint &b);
  friend bool operator<=(const bigint &a, int x);
  friend bool operator<=(int x, const bigint &b);
  friend bool operator<=(const bigint &a, long long x);
  friend bool operator<=(long long x, const bigint &b);

  friend bool operator>=(const bigint &a, const bigint &b);
  friend bool operator>=(const bigint &a, int x);
  friend bool operator>=(int x, const bigint &b);
  friend bool operator>=(const bigint &a, long long x);
  friend bool operator>=(long long x, const bigint &b);

  friend bool operator==(const bigint &a, const bigint &b);
  friend bool operator==(const bigint &a, int x);
  friend bool operator==(int x, const bigint &b);
  friend bool operator==(const bigint &a, long long x);
  friend bool operator==(long long x, const bigint &b);

  friend bool operator!=(const bigint &a, const bigint &b);
  friend bool operator!=(const bigint &a, int x);
  friend bool operator!=(int x, const bigint &b);
  friend bool operator!=(const bigint &a, long long x);
  friend bool operator!=(long long x, const bigint &b);

  bigint &operator+=(int x);
  bigint &operator+=(long long x);
  bigint &operator+=(const bigint &b);

  bigint &operator-=(int x);
  bigint &operator-=(long long x);
  bigint &operator-=(const bigint &b);

  bigint &operator*=(int x);
  bigint &operator*=(const bigint &b);

  bigint &operator/=(int x);
  bigint &operator/=(const bigint &b);

  bigint &operator%=(int x);
  bigint &operator%=(const bigint &b);

  bigint &abs();
  bigint &neg();
  bool mod2();
  long double eval() const;
  friend bigint operator-(const bigint &a);

  friend istream &operator>>(istream &in, bigint &b);
  friend ostream &operator<<(ostream &out, const bigint &b);

  explicit operator int() { return this->to_int(); }
  explicit operator long long() { return this->to_long_long(); }
  operator void *() { return this->is_zero() ? 0 : this; }

private:
  static void append_to_string(string &s, long long x);

  bool is_neg;
  vector<int> s;

  void init();
  void initstr(const char *str);
  bigint &canonicity();
  friend int __builtin_simple_division(const bigint &a, const bigint &b);
};

void bigint::init() { is_neg = false, s = {0}; }

void bigint::initstr(const char *str) {
  this->init();

  int L = strlen(str);
  if (*str == 45)
    is_neg = true, ++str, --L;
  if (!L || (L == 1 && *str == 48)) {
    is_neg = false;
    return;
  }

  int i;
  char tok[10];
  tok[9] = 0;
  s.clear();

  for (i = 1; i * 9 <= L; ++i) {
    memcpy(tok, str + (L - i * 9), 9);
    s.push_back((int)strtol(tok, NULL, 10));
  }

  if (L % 9) {
    memcpy(tok, str, L % 9), tok[L % 9] = 0;
    s.push_back((int)strtol(tok, NULL, 10));
  }

  this->canonicity();
}

bigint &bigint::canonicity() {
  for (; s.size() > 1 && !s.back(); s.pop_back())
    ;
  if (this->is_zero())
    is_neg = false;
  return *this;
}

bigint::bigint() { this->init(); }
bigint::bigint(const string &s) { this->initstr(s.c_str()); }
bigint::bigint(const char *s) { this->initstr(s); }

bigint::bigint(int x) {
  this->init(), x < 0 && (is_neg = true, x = -x), s.back() = x % BASE;
  if (x >= BASE)
    s.push_back(x / BASE);
}

bigint::bigint(long long x) {
  this->init(), x < 0 && (is_neg = true, x = -x), s.back() = x % BASE;
  if (x >= BASE)
    s.push_back(x / BASE % BASE);
  if (x >= BASE2)
    s.push_back(x / BASE2);
}

bigint::bigint(const bigint &b) { is_neg = b.is_neg, s = b.s; }

bigint::bigint(const vector<int> &digits, bool is_negative) {
  is_neg = is_negative, s = digits, this->canonicity();
}

bool bigint::is_zero() const { return s.size() == 1 && s.back() == 0; }

string bigint::to_string() const {
  string ret;
  if (is_neg && !this->is_zero())
    ret.push_back(45);

  int i = (int)s.size() - 1;
  char tok[10];
  for (sprintf(tok, "%d", s[i]); ret += tok, i--; sprintf(tok, "%09d", s[i]))
    ;

  return ret;
}

int bigint::to_int() const {
  long long v = this->to_long_long();
  return v >= INT_MAX ? INT_MAX : v <= INT_MIN ? INT_MIN : (int)v;
}

long long bigint::to_long_long() const {
  unsigned long long v = 0;
  switch (s.size()) {
  case 3u:
    if (s[2] > 9)
      return is_neg ? LLONG_MIN : LLONG_MAX;
    v += s[2] * BASE2;
  case 2u:
    v += (long long)s[1] * BASE;
  case 1u:
    v += s[0];
    break;
  default:
    return is_neg ? LLONG_MIN : LLONG_MAX;
  }
  return is_neg ? (v > LLONG_MAX ? LLONG_MIN : -(long long)v)
                : (v >= LLONG_MAX ? (long long)LLONG_MAX : (long long)v);
}

int bigint::compare_with(const bigint &b) const {
  if (is_neg != b.is_neg)
    return is_neg ? -1 : 1;
  if (s.size() != b.s.size())
    return (s.size() < b.s.size()) ^ is_neg ? -1 : 1;
  for (int i = (int)s.size() - 1; i >= 0; --i)
    if (s[i] != b.s[i])
      return (s[i] < b.s[i]) ^ is_neg ? -1 : 1;
  return 0;
}

int bigint::compare_with(int x) const {
  return this->compare_with((long long)x);
}

int bigint::compare_with(long long x) const {
  long long v = this->to_long_long();
  if (x == LLONG_MAX)
    return v != x ? -1 : this->to_string() != "9223372036854775807";
  if (x == LLONG_MIN)
    return v != x ? 1 : -(this->to_string() != "-9223372036854775808");
  return v < x ? -1 : v > x;
}

bigint &bigint::operator=(const string &s) {
  return this->initstr(s.c_str()), *this;
}

bigint &bigint::operator=(const char *s) { return this->initstr(s), *this; }

bigint &bigint::operator=(int x) {
  this->init(), x < 0 && (is_neg = true, x = -x), s.back() = x % BASE;
  if (x >= BASE)
    s.push_back(x / BASE);
  return *this;
}

bigint &bigint::operator=(long long x) {
  this->init(), x < 0 && (is_neg = true, x = -x), s.back() = x % BASE;
  if (x >= BASE)
    s.push_back(x / BASE % BASE);
  if (x >= BASE2)
    s.push_back(x / BASE2);
  return *this;
}

bigint &bigint::operator=(const bigint &b) {
  return is_neg = b.is_neg, s = b.s, *this;
}

#define __bigint_COMPARATOR__(op, neg)                                         \
  bool operator op(const bigint &a, const bigint &b) {                         \
    return a.compare_with(b) op 0;                                             \
  }                                                                            \
  bool operator op(const bigint &a, int x) { return a.compare_with(x) op 0; }  \
  bool operator op(int x, const bigint &b) { return b.compare_with(x) neg 0; } \
  bool operator op(const bigint &a, long long x) {                             \
    return a.compare_with(x) op 0;                                             \
  }                                                                            \
  bool operator op(long long x, const bigint &b) {                             \
    return b.compare_with(x) neg 0;                                            \
  }

__bigint_COMPARATOR__(<, >);
__bigint_COMPARATOR__(>, >);
__bigint_COMPARATOR__(<=, >=);
__bigint_COMPARATOR__(>=, <=);
__bigint_COMPARATOR__(==, ==);
__bigint_COMPARATOR__(!=, !=);
#undef __bigint_COMPARATOR__

bigint &bigint::abs() { return is_neg = false, *this; }
bigint &bigint::neg() { return is_neg ^= !this->is_zero(), *this; }

bigint operator-(const bigint &a) {
  bigint ret = a;
  return ret.neg();
}

istream &operator>>(istream &in, bigint &b) {
  string s;
  return in >> s, b.initstr(s.c_str()), in;
}
ostream &operator<<(ostream &out, const bigint &b) {
  return out << b.to_string();
}

void __builtin_abs_add_long_long(vector<int> &s, long long x) {
  if (s.size() < 3u)
    s.resize(3);
  s[0] += x % bigint::BASE, s[1] += x / bigint::BASE % bigint::BASE,
      s[2] += x / bigint::BASE2;
  int i, n = (int)s.size();
  s.push_back(0);
  for (i = 0; i < n; ++i)
    if (s[i] >= bigint::BASE)
      s[i + 1] += s[i] / bigint::BASE, s[i] %= bigint::BASE;
}

void __builtin_abs_sub_long_long(vector<int> &s, long long x) {
  if (s.size() < 3u)
    s.resize(3);
  s[0] -= x % bigint::BASE, s[1] -= x / bigint::BASE % bigint::BASE,
      s[2] -= x / bigint::BASE2;
  int i, n = (int)s.size(), d;
  for (i = 0; i < n - 1; ++i)
    if (s[i] < 0)
      s[i + 1] += d = (s[i] + 1) / bigint::BASE - 1, s[i] -= d * bigint::BASE;
}

bigint &bigint::operator+=(int x) { return *this += (long long)x; }

bigint &bigint::operator+=(long long x) {
  if (!x)
    return *this;
  if (x == LLONG_MIN)
    return *this -= bigint("9223372036854775808");
  if (x < 0)
    return *this -= -x;
  if (!is_neg)
    __builtin_abs_add_long_long(s, x);
  else
    switch (this->compare_with(-x)) {
    case -1:
      __builtin_abs_sub_long_long(s, x);
      break;
    case 0:
      return this->init(), *this;
    case 1:
      return *this = bigint(this->to_long_long() + x);
    }
  return this->canonicity();
}

bigint &bigint::operator-=(int x) { return *this -= (long long)x; }

bigint &bigint::operator-=(long long x) {
  if (!x)
    return *this;
  if (x == LLONG_MIN)
    return *this += bigint("9223372036854775808");
  if (x < 0)
    return *this += -x;
  if (is_neg)
    __builtin_abs_add_long_long(s, x);
  else
    switch (this->compare_with(x)) {
    case -1:
      return *this = bigint(this->to_long_long() - x);
    case 0:
      return this->init(), *this;
    case 1:
      __builtin_abs_sub_long_long(s, x);
      break;
    }
  return this->canonicity();
}

bigint &bigint::operator*=(int x) {
  if (!x || this->is_zero())
    return this->init(), *this;
  if (x < 0)
    is_neg ^= 1, x = -x;
  int i, n = s.size();
  long long cur = 0;
  s.push_back(0), s.push_back(0);
  for (i = 0; i < n + 2; ++i) {
    cur = (long long)x * s[i] + cur;
    s[i] = cur % BASE, cur /= BASE;
  }
  return this->canonicity();
}

bigint &bigint::operator/=(int x) {
  if (this->is_zero())
    return *this;
  bool neg = is_neg;
  if (x < 0)
    is_neg ^= 1, x = -x;
  int i, n = s.size();
  long long cur = 0;
  for (i = n - 1; i >= 0; --i) {
    cur = cur * BASE + s[i];
    s[i] = cur / x, cur -= (long long)x * s[i];
  }
  if (neg && cur)
    __builtin_abs_add_long_long(s, 1ll);
  return this->canonicity();
}

bool bigint::mod2() {
  return s.empty() ? 0 : s[0] & 1;
}
long double bigint::eval() const {
  long double val = 0;
  for(int i = int(s.size()) - 1; ~i; i--) {
    val = val * BASE + s[i];
  }
  return val * (is_neg ? -1 : 1);
}

bigint &bigint::operator%=(int x) {
  if (x < 0)
    x = -x;
  int i, n = s.size();
  long long cur = 0;
  for (i = n - 1; i >= 0; --i)
    cur = (cur * BASE + s[i]) % x;
  if (this->is_neg)
    cur = (cur ? x - cur : 0);
  return *this = bigint((int)cur);
}

bigint operator+(const bigint &a, int x) {
  bigint ret = a;
  return ret += x;
}
bigint operator+(int x, const bigint &a) {
  bigint ret = a;
  return ret += x;
}
bigint operator+(const bigint &a, long long x) {
  bigint ret = a;
  return ret += x;
}
bigint operator+(long long x, const bigint &a) {
  bigint ret = a;
  return ret += x;
}

bigint operator-(const bigint &a, int x) {
  bigint ret = a;
  return ret -= x;
}
bigint operator-(int x, const bigint &a) { return -(a - x); }
bigint operator-(const bigint &a, long long x) {
  bigint ret = a;
  return ret -= x;
}
bigint operator-(long long x, const bigint &a) { return -(a - x); }

bigint operator*(const bigint &a, int x) {
  bigint ret = a;
  return ret *= x;
}
bigint operator*(int x, const bigint &a) {
  bigint ret = a;
  return ret *= x;
}

bigint operator/(const bigint &a, int x) {
  bigint ret = a;
  return ret /= x;
}

bigint operator%(const bigint &a, int x) {
  bigint ret = a;
  return ret %= x;
}

bigint operator+(const bigint &a, const bigint &b) {
  if (a.is_neg == b.is_neg) {
    int i, n = a.s.size(), m = b.s.size(), min, max;
    const bigint &big = (n < m ? (min = n, max = m, b) : (min = m, max = n, a));
    bigint ret;
    ret.is_neg = a.is_neg, ret.s.resize(max + 1);
    for (i = 0; i < min; ++i) {
      ret.s[i] += a.s[i] + b.s[i];
      if (ret.s[i] >= bigint::BASE)
        ret.s[i] -= bigint::BASE, ++ret.s[i + 1];
    }
    for (; i < max; ++i) {
      ret.s[i] += big.s[i];
      if (ret.s[i] >= bigint::BASE)
        ret.s[i] -= bigint::BASE, ++ret.s[i + 1];
    }
    return ret.canonicity();
  } else
    return a.is_neg ? b - -a : a - -b;
}

bigint operator-(const bigint &a, const bigint &b) {
  if (!a.is_neg && !b.is_neg)
    switch (a.compare_with(b)) {
    case -1:
      return -(b - a);
    case 0:
      return bigint();
    default: {
      int i, n = a.s.size(), m = b.s.size();
      bigint ret = a;
      for (i = 0; i < n; ++i) {
        i < m ? ret.s[i] -= b.s[i] : 0;
        if (ret.s[i] < 0)
          ret.s[i] += bigint::BASE, --ret.s[i + 1];
      }
      return ret.canonicity();
    }
    }
  else if (a.is_neg && b.is_neg)
    return -b - -a;
  else
    return a.is_neg ? -(-a + b) : a + -b;
}

bigint operator*(const bigint &a, const bigint &b) {
  if (a.is_zero() || b.is_zero())
    return bigint();
  int i, j, k, n = a.s.size(), m = b.s.size();
  long long cur = 0, carry = 0;
  bigint ret;
  ret.is_neg = a.is_neg ^ b.is_neg, ret.s.resize(n + m);
  for (k = 0; k < n + m; ++k) {
    for (k < m ? (i = 0, j = k) : (i = k - m + 1, j = m - 1); i < n && j >= 0;
         ++i, --j)
      cur = (cur + (long long)a.s[i] * b.s[j]), carry += cur / bigint::BASE,
      cur %= bigint::BASE;
    ret.s[k] = (int)cur, cur = carry % bigint::BASE, carry /= bigint::BASE;
  }
  return ret.canonicity();
}

int __builtin_simple_division(const bigint &a, const bigint &b) {
  switch (a.compare_with(b)) {
  case -1:
    return 0;
  case 0:
    return 1;
  }
  int n = a.s.size(), m = b.s.size(), guess_quo;
  long long B;
  if (m == 1)
    return a.to_long_long() / b.s.back();
  B = (long long)b.s.back() * bigint::BASE + b.s[m - 2];
  if (n == m + 1)
#ifdef _GLIBCXX_USE_INT128
    guess_quo =
        (((__int128)a.s.back() * bigint::BASE + a.s[n - 2]) * bigint::BASE +
         a.s[n - 3] + 1) /
        B;
#else
    guess_quo =
        (((long double)a.s.back() * bigint::BASE + a.s[n - 2]) * bigint::BASE +
         a.s[n - 3] + 1) /
        B,
    guess_quo += 2;
#endif
  else
    guess_quo = ((long long)a.s.back() * bigint::BASE + a.s[n - 2] + 1) / B;
  for (; a < b * guess_quo; --guess_quo)
    ;
  return guess_quo;
}

bigint operator/(const bigint &a, const bigint &b) {
  if (a.is_zero() || b.is_zero())
    return a;
  bool neg = a.is_neg;
  int i, n = a.s.size();
  bigint cur, ret, B = b;
  ret.is_neg = a.is_neg ^ b.is_neg, ret.s.resize(n);
  B.abs();
  for (i = n - 1; i >= 0; --i) {
    cur = cur * bigint::BASE + a.s[i];
    ret.s[i] = __builtin_simple_division(cur, B);
    cur -= B * ret.s[i];
  }
  if (neg && !cur.is_zero())
    __builtin_abs_add_long_long(ret.s, 1ll);
  return ret.canonicity();
}

bigint operator%(const bigint &a, const bigint &b) { return a - a / b * b; }

bigint &bigint::operator+=(const bigint &b) { return *this = *this + b; }

bigint &bigint::operator-=(const bigint &b) { return *this = *this - b; }

bigint &bigint::operator*=(const bigint &b) { return *this = *this * b; }

bigint &bigint::operator/=(const bigint &b) { return *this = *this / b; }

bigint &bigint::operator%=(const bigint &b) { return *this = *this % b; }
} 
using namespace decimal;

using bi = bigint;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

// ---------- templates above ----------

struct FastMod {
  ull b, m;
  void init(ull p) {b = p, m = ull((LL(1) << 64) / p);}
  ull rd(ull a) {
    ull q = (LL(a) * m) >> 64;
    ull r = a - q * b;
    return r >= b ? r - b : r;
  }
};

constexpr int L = 610;
constexpr int N = 32;
constexpr int M = 1e6 + 5;

bi rpos(bi k) {return k * (k + 1) / 2 + k;}

ll P[M], Q[M];
map<bi, bi> mpp;
bi calcP(bi n) {
  if(n < M) return P[int(n)];
  auto it = mpp.find(n);
  if(it != mpp.end()) return it->second;
  bi l = 1, r = min(n - 1, bi("141500000000000000000"));
  while(l < r) {
    bi m = (l + r + 2) / 2;
    if(m * (m + 1) <= n + n) l = m;
    else r = m - 1;
  }
  return mpp[n] = l;
}

struct solver {
  int mod, inv;
  FastMod R;
  void addt(int &x, int y) {
    x += y, x >= mod && (x -= mod);
  }
  int add(int x, int y) {
    return x += y, x >= mod && (x -= mod), x;
  }
  int ksm(int a, int b) {
    int s = 1;
    while(b) {
      if(b & 1) s = R.rd(1ll * s * a);
      a = R.rd(1ll * a * a), b >>= 1;
    }
    return s;
  }
  int de[N], iv[N];
  int f[4][N], F[4][N], F2[4][N], g[4][L];
  int eval(int *f, bi _x) {
    int x = int(_x % mod);
    static int pre[N], suf[N + 1];
    pre[0] = suf[N] = 1;
    for(int i = 1; i < N; i++) {
      pre[i] = pre[i - 1];
      pre[i] = R.rd(1ll * pre[i] * (x + mod - i));
    }
    for(int i = N - 1; i; i--) {
      suf[i] = suf[i + 1];
      suf[i] = R.rd(1ll * suf[i] * (x + mod - i));
    }
    int ans = 0;
    for(int i = 1; i < N; i++) {
      int nume = R.rd(1ll * pre[i - 1] * suf[i + 1]);
      addt(ans, R.rd(R.rd(1ll * nume * f[i]) * iv[i]));
    }
    return ans;
  }
  int eval(int *f, bi l, bi r) {
    return add(eval(f, r), mod - eval(f, l));
  }
  void init(int p) {
    R.init(mod = p);
    for(int i = 1; i < N; i++) {
      de[i] = 1;
      for(int j = 1; j < N; j++) {
        if(i != j) de[i] = R.rd(1ll * de[i] * (i + mod - j));
      }
      iv[i] = ksm(de[i], mod - 2);
    }
    for(int k = 1; k < N; k++) {
      f[0][k] = k + 1;
      F[0][k] = add(F[0][k - 1], f[0][k]);
      F2[0][k] = add(F2[0][k - 1], R.rd(1ll * f[0][k] * k));
    }
    for(int i = 1; i < 4; i++) {
      for(int k = 1; k < N; k++) {
        int rk = int(rpos(k)), lk = rk - (k + 1);
        f[i][k] = eval(F2[i - 1], lk, rk);
        addt(f[i][k], R.rd(1ll * (mod - lk) * eval(F[i - 1], lk, rk)));
        addt(f[i][k], mod - R.rd(1ll * (k + 1) * eval(F[i - 1], rk)));
        F[i][k] = add(F[i][k - 1], f[i][k]);
        F2[i][k] = add(F2[i][k - 1], R.rd(1ll * f[i][k] * k));
      }
    }
    for(int i = 0; i < 4; i++) {
      for(int j = 1; j < L; j++) {
        g[i][j] = add(g[i][j - 1], R.rd(1ll * eval(f[i], j) * Q[j]));
      }
    }
    // for(int i = 0; i < 4; i++) {
    //   for(int j = 0; j < N; j++) {
    //     cout << i << " " << j << " " << f[i][j] << " " << F[i][j] << " " << F2[i][j] << "\n";
    //   }
    // }
  }
  int calc(int dep, bi n);
  int calcQ(bi n);
  map<bi, int> mp[4], mpq;
} f[9];

int solver::calc(int dep, bi n) {
  if(n < L) return g[dep][int(n)];
  auto it = mp[dep].find(n);
  if(it != mp[dep].end()) return it->second;
  bi p = calcP(n), rp = rpos(p - 1);
  int coef = eval(F2[dep], rp, n);
  addt(coef, R.rd(1ll * int(mod - rp % mod) * eval(F[dep], rp, n)));
  int res = R.rd(1ll * coef * calcQ(p));
  addt(res, R.rd(1ll * eval(F[dep], n) * calc(0, p - 1)));
  addt(res, calc(dep + 1, p - 1));
  return mp[dep][n] = res;
}

int solver::calcQ(bi n) {
  if(n < M) return R.rd(Q[int(n)]);
  auto it = mpq.find(n);
  if(it != mpq.end()) return it->second;
  bi p = calcP(n), rp = rpos(p - 1);
  int coef = int((n - rp) % mod);
  int res = add(calc(0, p - 1), R.rd(1ll * coef * calcQ(p)));
  return mpq[n] = res;
}

bi PR = 1;
void init() {
  for(int i = 1, c = 1; c < M; i++) {
    for(int j = 1; j <= i + 1 && c < M; j++) {
      P[c++] = i;
    }
  }
  Q[1] = 1;
  for(int i = 2; i < M; i++) {
    Q[i] = Q[i - 1] + Q[P[i]];
  }
  for(int i = 1e9, c = 0; c < 9; i++) {
    bool prime = 1;
    for(int j = 2; j * j <= i && prime; j++) {
      prime &= i % j > 0;
    }
    if(prime) f[c++].init(i), PR *= i;
  }
  for(int i = 0; i < 9; i++) {
    f[i].inv = f[i].ksm(int((PR / f[i].mod) % f[i].mod), f[i].mod - 2);
  }
}

void solve(int T) {
  bi n, ans = 0;
  cin >> n;
  // n = 1;
  // for(int i = 1; i <= 40; i++) n *= 10;
  // n -= T;
  for(int i = 0; i < 9; i++) {
    int res = f[i].calcQ(n);
    ans += (PR / f[i].mod) * res * f[i].inv;
  }
  cout << ans % PR << "\n";
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  init();
  int T = 1;
  cin >> T;
  // T = 1e4;
  while(T--) solve(T);
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/