m=998244353
for _ in' '*int(input()):N=int(input());M=N*(N-1)//2;print((N*pow(2,M,m)-pow(2,M-2*N+3,m)*(N-1)*pow(3,N-2,m))%m)