Given a positive integer $n$ and a sequence of positive integers $a_1, a_2, \dots, a_n$, where $a_i$ represents the color of the $i$-th point, find the number of simple undirected graphs $G$ with $n$ vertices that satisfy the following conditions:

1. No two edges share a common endpoint. That is, $G$ is a matching.
2. For every edge, its two endpoints have the same color.
3. For two distinct edges $e_1=(u_1, v_1)$ ($u_1 < v_1$) and $e_2=(u_2, v_2)$ ($u_2 < v_2$), we say $e_1$ and $e_2$ intersect if $u_1 < u_2 < v_1 < v_2$ or $u_2 < u_1 < v_2 < v_1$. The number of unordered pairs $(e_1, e_2)$ such that $e_1$ and $e_2$ intersect must be even.

Since the answer may be very large, output it modulo $998244353$. Each test case contains $T$ datasets.

Input

The first line contains a positive integer $T$. This is followed by $T$ datasets, with a blank line between each pair of datasets.

The first line of each dataset is a positive integer $n$, and the second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, separated by spaces.

Output

Output $T$ lines, each containing a non-negative integer representing the answer.

Examples

Input 1

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

Output 1

1
3
9

Note 1

For the first dataset, since all points have distinct colors, no edges can be formed. With zero edges, the number of intersections is $0$, so the answer is $1$.

For the second dataset, there are $4$ possible matchings. The matching where both $(1, 3)$ and $(2, 4)$ are connected has $1$ intersection, which is invalid. Thus, the answer is $3$.

For the third dataset, connecting $0$ edges or $1$ edge is always valid. Connecting two edges $(1, 3)$ and $(2, 4)$ is invalid. Thus, the answer is $9$.

Constraints

For test cases $1 \sim 2$, $n \le 13$.

For test cases $3 \sim 4$, all $a_i$ are identical.

For test cases $5 \sim 10$, $a_i \le 10$.

For test cases $11 \sim 14$, $n \le 300$.

For test cases $15 \sim 20$, $n \le 2000$.

For $100\%$ of the data, $1 \le T \le 5, 1 \le n \le 2000, 1 \le a_i \le n$.