俾定一個長度為 $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