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