问题描述

求有多少个长度为$n$的排列，满足奇数位置比相邻的都小，偶数位置比相邻的都大。 保证$n$是奇数，对998244353取模。$T$组数据。

输入格式

第一行一个整数$T$。

后面$T$行，每行一个正奇数$n$。

输出格式

$T$行，每行一个数表示答案模998244353。

样例一

input

5
1
3
5
7
9

output

1
2
16
272
7936

数据规模

$10\%$的数据，满足$1 \leq n \leq 10$。

$20\%$的数据，满足$1 \leq n \leq 20$。

$40\%$的数据，满足$1 \leq n \leq 5000$。

$60\%$的数据，满足$1 \le n \le 10^5$。

$70\%$的数据，满足$1 \leq n \leq 2*10^5$。

$80\%$的数据，满足$1 \leq n \leq 5*10^5$。

$100\%$的数据，满足$1 \le n \le 10^6,1 \le T \le 10^4$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$