길이가 $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