Gegeben ist eine Permutation $p$ der Länge $n$.

Jede Operation wählt zufällig und mit gleicher Wahrscheinlichkeit eine ganze Zahl $i$ ($1 \le i \le n$) aus und sortiert anschließend das Präfixintervall $[1, i]$ sowie das Suffixintervall $[i + 1, n]$ der Permutation $p$ jeweils in aufsteigender Reihenfolge. Insbesondere ist für $i = n$ das Suffixintervall leer, was dem Sortieren der gesamten Permutation entspricht.

Du musst die erwartete Anzahl an Operationen bestimmen, die benötigt werden, bis die Permutation vollständig in aufsteigender Reihenfolge sortiert ist (das heißt, $p_j = j$).

Die Antwort ist modulo $998\,244\,353$ auszugeben.

Eingabe

Dieses Problem enthält mehrere Testfälle.

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die Anzahl der Testfälle.

Für jeden Testfall gilt:

• Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 500$), die Länge der Permutation.
• Die zweite Zeile enthält $n$ ganze Zahlen $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), welche die gegebene Permutation $p$ darstellen. Es wird garantiert, dass die gegebene Folge eine Permutation von $1 \sim n$ ist.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $2000$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit einer ganzen Zahl aus: die erwartete Anzahl an Operationen modulo $998\,244\,353$.

Beispiel

Eingabe

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

Ausgabe

748683267
2
670695427