죄수들에게 뇌물 주기

한 왕국에 직선 선분을 이루도록 지어진 감방들이 있다(번호는 1부터 P까지이다). i번 감방과 i+1번 감방은 서로 인접하며, 인접한 감방에 있는 죄수들을 "neighbours."라고 부른다. 창문이 있는 벽이 인접한 감방들을 분리하며, 이웃한 죄수들은 그 창문을 통해 의사소통할 수 있다.

모든 죄수는 한 죄수가 석방될 때까지 평화롭게 지낸다. 그런 일이 일어나면 석방된 죄수의 이웃들이 이를 알게 되고, 각자 자신의 반대편 이웃에게 이 사실을 전한다. 그 죄수도 자신의 반대편 이웃에게 이를 전하며, 이런 식으로 다른 이웃이 없는 죄수에게 도달할 때까지 계속한다(그가 1번 감방이나 P번 감방에 있거나, 반대편의 인접한 감방이 비어 있기 때문이다). 다른 죄수가 석방되었다는 사실을 알게 된 죄수는 금화 하나를 뇌물로 받지 않으면 화가 나서 자기 감방의 모든 것을 부순다. 따라서 A번 감방의 죄수를 석방한 뒤에는 A번 감방의 양쪽에 수감된 모든 죄수에게, 1번 감방이나 P번 감방 또는 빈 감방에 이를 때까지 뇌물을 주어야 한다.

각 감방에는 처음에 정확히 한 명의 죄수가 수감되어 있고, 하루에 단 한 명의 죄수만 석방할 수 있다고 가정한다. Q일 동안 석방할 Q명의 죄수 목록이 주어질 때, 죄수들을 어떤 순서로든 석방할 수 있다면 뇌물로 필요한 금화 총개수의 최솟값을 구한다.

각 뇌물의 효력은 하루 동안만 지속된다는 점에 유의한다. 어제 뇌물을 받은 죄수가 오늘 또 다른 죄수가 석방되었다는 소식을 들으면, 그에게 다시 뇌물을 주어야 한다.

제한

메모리 제한: 1 GB. 1 ≤ N ≤ 100 Q ≤ P 각 감방 번호는 1 이상 P 이하이다.

작은 데이터 세트

시간 제한: 20초. 1 ≤ P ≤ 100 1 ≤ Q ≤ 5

큰 데이터 세트

시간 제한: 30초. 1 ≤ P ≤ 10000 1 ≤ Q ≤ 100

입력의 첫 줄에는 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다. 각 케이스는 2개의 줄로 구성된다. 첫 줄의 형식은 다음과 같다.

P Q

여기서 P는 감방의 수이고 Q는 석방할 죄수의 수이다. 그다음 줄에는 석방할 죄수들이 있는 서로 다른 Q개의 감방 번호가 공백으로 구분되어 오름차순으로 주어진다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Case #X: C

여기서 X는 1부터 시작하는 케이스 번호이고, C는 뇌물로 필요한 금화 개수의 최솟값이다.

두 번째 예제 케이스에서는 먼저 14번 감방의 사람을 석방하고, 그다음 6번 감방, 이어서 3번 감방의 사람을 석방한다. 필요한 금화의 개수는 19 + 12 + 4 = 35이다. 대신 6번 감방의 사람을 먼저 석방하면 비용은 19 + 4 + 13 = 36이 된다.