시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 708 | 100 | 81 | 24.545% |
데브시스터즈의 사내 레스토랑 스테이지 2에서는 총 M 가지의 음식을 만들 수 있으며 각 음식에는 1번부터 M 번까지 번호가 붙어 있다.
데브시스터즈 직원들은 매 끼니마다 스테이지 2에서 제공한 N 가지의 음식 중 하나를 골라서 먹을 수 있으며 스테이지 2에서 끼니마다 제공하는 음식은 다음과 같이 정해진다.
지난 끼니에 K 번 음식을 제공했다면, 이번 끼니에는 K+1번 음식을 제공한다. 단, 지난 끼니에 M 번 음식이 제공된 경우에는 이번 끼니에 1번 음식을 제공한다.
데브시스터즈에 처음 입사한 영희는 이 사실을 알고 스테이지 2에서 제공하는 음식의 조합이 몇 가지 인지 궁금해졌다. 그러나 영희는 일이 바쁘기 때문에 여러분에게 이번 끼니에 제공한 음식을 알려주면서 도움을 요청하였다. 여러분이 영희를 도와 음식 조합의 가짓수를 세어 주자.
첫 번째 줄에 테스트 케이스의 개수 T 가 주어진다.
각 케이스의 첫 줄에 스테이지2에서 만들 수 있는 음식의 가짓수 M, 끼니마다 제공되는 음식의 가짓수 N(1 ≤ N ≤ M ≤ 1,000,000)이 주어진다.
그 다음 N줄에 이번 끼니에 나온 음식들의 번호 xi (1 ≤ xi ≤ M)가 주어진다. 이 번호들은 모두 다르며 오름차순으로 정렬되어 있다.
각 테스트 케이스마다 한 줄씩 음식 조합의 가짓수를 출력한다.
2 6 3 1 3 5 16 4 1 3 9 11
2 8