Cho một hoán vị $p$ có độ dài $n$.

Mỗi thao tác chọn ngẫu nhiên một số nguyên $i$ với xác suất bằng nhau ($1 \le i \le n$), sau đó lần lượt sắp xếp đoạn tiền tố $[1, i]$ và đoạn hậu tố $[i + 1, n]$ của hoán vị $p$ theo thứ tự tăng dần. Đặc biệt, khi $i = n$, đoạn hậu tố rỗng, tương đương với việc sắp xếp toàn bộ hoán vị.

Bạn cần tìm kỳ vọng số thao tác cần thiết cho đến khi hoán vị cuối cùng được sắp xếp hoàn toàn theo thứ tự tăng dần (tức là $p_j = j$).

Kết quả được lấy theo modulo $998\,244\,353$.

Dữ liệu vào

Bài toán này gồm nhiều bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$), là số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 500$), là độ dài của hoán vị.
• Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), biểu thị hoán vị $p$ đã cho. Dãy số đã cho được đảm bảo là một hoán vị của $1 \sim n$.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2000$.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên là kỳ vọng số thao tác theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào

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

Kết quả

748683267
2
670695427