시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 3 3 60.000%

문제

힙찌리 쇼미충 정주경은 음악 듣는 것을 좋아한다. 주경이는 음악을 들을 때 음악 플레이어의 shuffle 기능을 이용한다. 음악 플레이어는 랜덤으로 순열을 생성하여 플레이리스트의 음악을 재생하고, 모든 음악이 다 재생되면 다시 셔플이 되어 음악이 또 재생이 된다.

주경이는 이제껏 재생이 된 음악 목록을 가지고 있었는데, 이 재생 목록이 처음 음악이 재생될 때부터 완벽하게 기록을 하지 않았다는 것을 알게되었다. 이 기록을 가지고 주경이는 다음 셔플이 어떻게 될지를 알고싶어한다.

플레이 리스트의 음악의 수를 s라 할 때 음악 재생 목록을 길이 s인 구간으로 나눌 수 있는데, 처음과 마지막 구간은 s보다 작게끔 나눌수도 있다. 이 때 각 구간의 음악은 겹쳐서는 안된다.

입력

첫째 줄에는 테스트케이스의 수가 주어진다. 최대 100이다.

그 이후 각 테스트케이스마다 첫째 줄에는 s와 n(1 ≤ s, n ≤ 100 000)이 주어진다. s는 플레이리스트의 곡의 수이고, n은 이제껏 재생된 곡 목록의 곡의 수이다.

둘째 줄에는 n개의 x1, x2, . . . , xn (1 ≤ xi ≤ s) 재생된 음악이 주어진다.

출력

각 테스트 케이스마다

첫째 줄에 다음 셔플이 어떻게 되는 지 경우의 수를 출력한다. 만약 가능한 경우의 수가 없다면 0을 출력한다.

예제 입력

4
4 10
3 4 4 1 3 2 1 2 3 4
6 6
6 5 4 3 2 1
3 5
3 3 1 1 1
7 3
5 7 3

예제 출력

1
6
0
7

힌트