Diberikan sebuah permutasi $p$ dengan panjang $n$.

Setiap operasi memilih secara acak sebuah bilangan bulat $i$ dengan peluang yang sama ($1 \le i \le n$), lalu mengurutkan interval prefiks $[1, i]$ dan interval sufiks $[i + 1, n]$ dari permutasi $p$ secara menaik. Secara khusus, ketika $i = n$, interval sufiksnya kosong, yang setara dengan mengurutkan seluruh permutasi.

Anda perlu mencari nilai ekspektasi jumlah operasi yang diperlukan hingga permutasi akhir menjadi terurut sepenuhnya secara menaik (yaitu, $p_j = j$).

Jawaban harus diambil modulo $998\,244\,353$.

Masukan

Soal ini memiliki beberapa kasus uji.

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), yaitu jumlah kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 500$), yaitu panjang permutasi.
• Baris kedua berisi $n$ bilangan bulat $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), yang menyatakan permutasi $p$ yang diberikan. Dijamin bahwa barisan yang diberikan adalah permutasi dari $1 \sim n$.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2000$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat, yaitu nilai ekspektasi jumlah operasi modulo $998\,244\,353$.

Contoh

Masukan

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

Keluaran

748683267
2
670695427