mod = 998244353
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(1)
		continue
	ans = 0
	ans += (N + 1) * pow(2, N * (N - 1) // 2 - 1, mod)
	ans += pow(2, N * (N - 1) // 2 - (2 * N - 3)) * (N - 1) * (pow(4, N - 2, mod) - pow(3, N - 2, mod))
	ans %= mod
	print(ans)