mod = 998244353
inv_2 = (mod + 1) // 2
T = int(input())
for _ in range(T):
  N = int(input())
  E = N*(N-1) // 2
  ans = N * pow(2,E,mod) % mod
  # たどりつけないやつ考える.
  res = pow(3 * inv_2 % mod,N - 2,mod)
  res = res * pow(2,E - (N - 1),mod) % mod
  res = res * (N - 1) % mod
  print((ans - res) % mod)