È data una permutazione $p$ di lunghezza $n$.

Ogni operazione sceglie casualmente un intero $i$ con uguale probabilità ($1 \le i \le n$), e poi ordina rispettivamente l'intervallo prefisso $[1, i]$ e l'intervallo suffisso $[i + 1, n]$ della permutazione $p$ in ordine crescente. In particolare, quando $i = n$, l'intervallo suffisso è vuoto, il che equivale a ordinare l'intera permutazione.

Devi trovare il numero atteso di operazioni necessarie affinché la permutazione finale risulti completamente ordinata in ordine crescente (cioè $p_j = j$).

La risposta deve essere calcolata modulo $998\,244\,353$.

Input

Questo problema contiene più casi di test.

La prima riga contiene un intero $T$ ($1 \le T \le 100$), il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene un intero $n$ ($1 \le n \le 500$), la lunghezza della permutazione.
• La seconda riga contiene $n$ interi $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), che rappresentano la permutazione $p$ data. È garantito che la sequenza data sia una permutazione di $1 \sim n$.

È garantito che la somma di $n$ su tutti i casi di test non superi $2000$.

Output

Per ciascun caso di test, stampa una riga contenente un intero: il numero atteso di operazioni modulo $998\,244\,353$.

Esempio

Input

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

Output

748683267
2
670695427