Problem Description

给定 $n$ 个数 $a_{1...n}$，你需要求有几个 $\{1...n\}$ 的排列 $p$，满足对于 $1\leq i\leq n-2$，有 $min(a_{p_i},a_{p_{i+1}}) \leq min(a_{p_{i+1}},a_{p_{i+2}})$

由于答案可能过大，你只需要输出答案对 $998244353$ 取模后的值

Input

第一行一个正整数 $T(1\leq T\leq 100)$，表示数据组数。

接下来对于每组数据，第一行一个整数 $n (1\leq n\leq 1000)$

接下来一行 $n$ 个数字，表示 $a_{1...n}$，其中 $1\leq a_i\leq n$

Output

输出 $T$ 行，每行一个整数表示该组数据的答案

1
3
1 2 3

4