题目描述

给定正整数 $n$ 以及正整数序列 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 个点的颜色。
求同时满足如下条件的大小为 $n$ 的简单无向图 $G$ 的个数：

1. 边之间没有公共端点。即 $G$ 是一个匹配（可以是空匹配）。
2. 对于任一条边，它的两个端点的颜色相同。
3. 对两条不同的边 $e_1 = (u_1, v_1)$（$u_1 < v_1$）与 $e_2 = (u_2, v_2)$（$u_2 < v_2$），若
   $u_1 < u_2 < v_1 < v_2$ 或 $u_2 < u_1 < v_2 < v_1$，则称 $e_1$ 与 $e_2$ 相交。
   要求匹配中相交的无序边对 $(e_1, e_2)$ 的个数为偶数。

由于答案可能很大，对 $998244353$ 取模。每个数据点有 $T$ 组数据。

输入格式

第一行输入一个正整数 $T$。
接下来紧跟着 $T$ 组数据，两组数据之间会换一行。

每组数据的第一行是一个正整数 $n$，第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，两个正整数之间以一个空格隔开。

输出格式

$T$ 行，每行一个非负整数表示答案。

样例

输入

3
3
1 2 3
4
1 2 1 2
4
4 4 4 4

输出

1
3
9

样例解释

• 对于第一组数据，由于点的颜色互不相同，故不能连边，而不连边时交点数为 $0$，故答案为 $1$。
• 对于第二组数据，有 $4$ 个匹配，其中 $\{(1,3),(2,4)\}$ 全连的匹配的交点数为 $1$ 不合法，故答案为 $3$。
• 对于第三组数据，连 $0$ 条边或 $1$ 条边都是合法的，而若连两条边则连 $(1,3),(2,4)$ 是不合法的，故答案为 $9$。

数据范围与提示

对 $100\%$ 的数据：
$1 \le T \le 5$，$1 \le n \le 2000$，$1 \le a_i \le n$。