给你一个 $\{1, 2, \dots, N\}$ 的排列 $P$。

也就是说，$P$ 是一个长度为 $N$ 的数组，包含从 1 到 $N$ 的每个整数恰好一次。

你可以对其进行以下操作：

• 选择一个下标 $i$（$1 < i < |P|$）。
• 设 $P_i = \max(P_{i-1}, P_i, P_{i+1})$。
• 从 $P$ 中删除 $P_{i-1}$ 和 $P_{i+1}$。剩下的元素重新编号，下标从 1 开始。

每次此类操作都会使 $P$ 的长度减少 2。特别地，如果 $P$ 的长度为 1 或 2，则无法进行此操作。

求从 $P$ 开始，通过执行零次或多次该操作可以达到的不同数组的数量。

由于该值可能很大，你只需要求出其对 998 244 353 取模后的结果。

输入格式

输入按以下格式给出：

$$ \begin{array}{l} T \\ N \\ P_1 \ P_2 \ \cdots \ P_N \\ \vdots \end{array} $$

数据范围

• 所有输入值均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 5000$
• $1 \le P_i \le N$
• 对于所有 $i \ne j$，有 $P_i \ne P_j$。
• 保证所有测试用例的 $N^2$ 之和不超过 $5000^2$。

输出格式

对于每个测试用例，输出一个整数，表示对 $P$ 执行零次或多次操作可以达到的不同数组的数量，对 998 244 353 取模。

样例

输入格式 1

5
2
2 1
3
2 1 3
5
3 1 4 5 2
10
1 2 3 4 5 6 7 8 9 10
15
5 7 6 12 2 13 10 1 11 4 3 9 14 15 8

输出格式 1

1
2
5
55
365

说明

测试用例 1：无法进行任何操作。

测试用例 2：有两种可能性：

• 不进行任何操作。最终数组为 $[2, 1, 3]$。
• 对 $i = 2$ 进行一次操作。最终数组为 $[3]$。

这些是唯一可达的数组。