長さ $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$) が与えられます。
• 次の行には、与えられた順列 $p$ を表す $n$ 個の整数 $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$) が与えられます。与えられる数列は $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