#define MD 998244353
ll@T,L=2;mint a[1d6]{};Comb<mint>c;rep(T){ll@N;while(L<N)a[L]=c.C(L-1,L/2-1)*(L&1?-1:1)+2a[L-1],L++;wt(a[N-1]*(N&1^1));}