T=int(input())
p=998244353
for _ in range(T):
    N=int(input())
    ans=pow(2,N*(N-1)//2,p)+(N-1)*(pow(2,N*(N-1)//2,p)-pow(2,N*(N-1)//2-1-2*(N-2),p)*pow(3,N-2,p))
    print(ans%p)