#include <array>
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <string>

namespace {
using std::cin;
using std::cout;
using std::int64_t;
using std::size_t;

namespace base {
template <typename T, size_t... sizes>
struct NestedArray {};

template <typename T, size_t size, size_t... sizes>
struct NestedArray<T, size, sizes...> {
  using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};

template <typename T>
struct NestedArray<T> {
  using Type = T;
};

template <typename T, size_t... sizes>
using Array = typename NestedArray<T, sizes...>::Type;

void OptimizeIO() {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
}

void OptimizeIO(const std::string &input_file, const std::string &output_file) {
  static std::ifstream input_stream(input_file);
  static std::ofstream output_stream(output_file);
  cin.rdbuf(input_stream.rdbuf()), cout.rdbuf(output_stream.rdbuf());
  cin.tie(nullptr), cout.tie(nullptr);
}
}  // namespace base

using base::Array;

const int kP = 998244353, kInv2 = (kP + 1) / 2;

namespace mod {
inline void Mul(int &a, int b) { a = int64_t{a} * b % kP; }

int Pow(int a, int b) {
  int ans = 1, prod = a;

  while (b) {
    if (b & 1) Mul(ans, prod);
    Mul(prod, prod), b >>= 1;
  }

  return ans;
}

inline int Inv(int a) { return Pow(a, kP - 2); }
}  // namespace mod

const int kMaxLogN = 30;
int n;
int64_t ans;
Array<int64_t, kMaxLogN> c, sum;

inline int Calc(int n, int k) {
  int q = (n - 1) >> (k + 1), r = n - (q << (k + 1));
  return (q << k) + std::max(0, r - (1 << k));
}

void Dfs(int cur, bool f, int64_t sum) {
  if (cur == -1) {
    ans += std::max(sum % kP, int64_t{0});
    return;
  }

  if (sum + ::sum[cur] <= 0) return;

  if (sum - ::sum[cur] >= 0 && !f) {
    ans += sum << (cur + 1);
    return;
  }

  if (f) {
    if ((n - 1) >> cur & 1) {
      Dfs(cur - 1, true, sum - c[cur]);
      Dfs(cur - 1, false, sum + c[cur]);
    } else {
      Dfs(cur - 1, true, sum + c[cur]);
    }
  } else {
    Dfs(cur - 1, false, sum - c[cur]);
    Dfs(cur - 1, false, sum + c[cur]);
  }
}

void Solve() {
  cin >> n;

  for (int i = 0; i < kMaxLogN; ++i) {
    sum[i] = c[i] = int64_t{Calc(n, i)} << i;
    if (i) sum[i] += sum[i - 1];
  }

  ans = 0, Dfs(kMaxLogN - 1, true, 0);
  int inv = mod::Inv(n);
  cout << (ans % kP * inv % kP * inv + int64_t{n - 1} * kInv2) % kP << "\n";
}

int Main() {
  base::OptimizeIO();
  int t;
  cin >> t;
  while (t--) Solve();
  return 0;
}
}  // namespace

int main() { return Main(); }