#define MD 998244353
ll@T;rep(T){ll@N,@M,l;Mint D[M+1][3]{{1}};rep(i,M){auto&d=D[i],e=D[i+1];e[0]=d[0]+d[1]+d[2];e[1]=d[0]*N+d[1]*(N-1)+d[2]*(N-2);e[2]=(N>3)*sum[a,0,3](d[a]*((N-a)*(N-a-3)/2+a));}wt(D[M][0]+D[M][1]+D[M][2]);}