mod = 998244353
p = 3 * pow(2, mod - 2, mod)

def solve(n):
    if n == 1:
        return 1
    ans = n * pow(2, n * (n - 1) // 2, mod)
    res = pow(p, n - 2, mod) * pow(2, (n - 1) * (n - 2) // 2, mod) * (n - 1)
    return (ans - res) % mod


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