给定一个长度为 $n$ 的排列 $p$。

每次操作会等概率随机选择一个整数 $i$（$1 \le i \le n$），然后分别将排列 $p$ 的前缀区间 $[1, i]$ 和后缀区间 $[i + 1, n]$ 按升序排序。特别地，当 $i = n$ 时，后缀区间为空，这等价于将整个排列排序。

你需要求出直到最终排列完全按升序排好序（即 $p_j = j$）所需的期望操作次数。

答案对 $998\,244\,353$ 取模。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$（$1 \le n \le 500$），表示排列的长度。
• 第二行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$（$1 \le p_j \le n$），表示给定的排列 $p$。保证给定的序列是 $1 \sim n$ 的一个排列。

保证所有测试数据中 $n$ 的总和不超过 $2000$。

输出格式

对于每组测试数据，输出一行包含一个整数，表示期望操作次数对 $998\,244\,353$ 取模的结果。

样例

样例输入

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

样例输出

748683267
2
670695427