z = 998244353
for _ in range(int(input())):
    n = int(input()); m = n*(n-1)//2
    print(((pow(2,m,z)-pow(3,n-2,z)*pow(2,m-2*n+3,z)%z)*(n-1)+pow(2,m,z))%z if n>1 else 1)