小 Fiona 有 $n$ 个大小各异的积木，大小分别为 $a_1, a_2, \dots, a_n$，其中 $n$ 为偶数。有些积木的大小可能相同。她想把这些积木全部堆叠在一起，形成一个“花式堆叠”（fancy stack）。

设 $b_1, b_2, \dots, b_n$ 为从上到下堆叠的积木大小。由于 Fiona 使用了所有的积木，$b_1, b_2, \dots, b_n$ 必须是 $a_1, a_2, \dots, a_n$ 的一个排列。Fiona 认为，如果满足以下两个条件，这个堆叠就是“花式”的：

• 第二个积木严格大于第一个，且后续每个积木与前一个积木的大小关系交替为严格小于或严格大于。形式化地，$b_1 < b_2 > b_3 < b_4 > \dots > b_{n-1} < b_n$。
• 位于偶数位置的积木大小严格递增。形式化地，$b_2 < b_4 < b_6 < \dots < b_n$（注意 $n$ 为偶数）。

如果两个堆叠对应的序列 $b_1, b_2, \dots, b_n$ 在至少一个位置上不同，则认为它们是不同的堆叠。

Fiona 想知道她能用这些积木搭建出多少种不同的花式堆叠。由于大数字会让 Fiona 感到害怕，请输出该数量对 $998\,244\,353$ 取模的结果。

输入格式

每个输入包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 2500$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ —— Fiona 手中积木的数量（$2 \le n \le 5000$；$n$ 为偶数）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 按非递减顺序排列的积木大小（$1 \le a_1 \le a_2 \le \dots \le a_n \le n$）。

保证所有测试用例的 $n$ 之和不超过 $5000$。

输出格式

对于每个测试用例，输出搭建花式堆叠的方法数，对 $998\,244\,353$ 取模。

样例

输入 1

2
4
1 2 3 4
8
1 1 2 3 4 4 6 7

输出 1

2
4