Singin' in the Rain

2016 UCF 지역 프로그래밍 대회 때 Arup의 둘째 딸 Anya(당시 3살)는 Arup에게 Taylor Swift의 노래 "Wildest Dreams"를 계속 들려 달라고 졸랐다. 1년이 지난 지금 Anya의 음악 취향은 많이 자랐다. 같은 노래를 반복해서 듣는 대신, 이제는 같은 CD에 있는 서로 다른 곡들을 순서대로 듣고 싶어 한다.

올해 Anya가 가장 좋아하는 CD는 "Singing in the Rain"이다. 이 CD는 누나 Simran이 지역 극장의 "Singing in the Rain" 공연에 출연했을 때 얻은 것이다. Anya는 Arup과 차에 함께 탈 때마다 한 곡을 듣고, 그다음에 듣고 싶은 곡의 번호를 외친다. 문제는 Arup의 차에 있는 CD 플레이어가 꽤 단순하다는 점이다.

• 트랙 k의 재생이 끝나면 트랙 k+1이 재생된다. k가 마지막 트랙이면 CD가 처음으로 돌아가 트랙 1이 재생된다.
• Arup은 앞으로 버튼으로도 트랙을 바꿀 수 있다. 트랙 k의 재생이 끝났을 때 앞으로 버튼을 누르면 트랙 k+2가 재생된다. k가 마지막 트랙이고 k가 끝났을 때 앞으로 버튼을 누르면 CD가 돌아가 트랙 2가 다음에 재생된다. k가 마지막 바로 앞 트랙이고 k가 끝났을 때 앞으로 버튼을 누르면 트랙 1이 다음에 재생된다.
• Arup은 뒤로 버튼으로도 트랙을 바꿀 수 있다. 트랙 k의 재생이 끝났을 때 뒤로 버튼을 누르면 트랙 k가 다시 재생된다. k가 트랙 1이고 트랙 1의 재생이 끝난 직후 뒤로 버튼을 두 번 누르면 CD가 돌아가 트랙 t가 다음에 재생된다. 여기서 t는 CD의 트랙 수이다.

Arup은 앞으로 버튼이나 뒤로 버튼을 매우 많이 누르게 된다. Arup이 누르는 버튼 횟수를 최소로 하도록 도와라.

처음에 CD 플레이어는 Anya가 원하는 순서의 첫 곡을 재생하도록 준비되어 있으므로, 이 곡이 재생되기 위해 버튼을 누를 필요는 없다. 버튼을 눌러야 할 수도 있는 첫 시점은 순서상 첫 곡과 둘째 곡 사이, 즉 첫 곡이 재생된 뒤이다.

첫 줄에는 테스트 케이스의 수를 나타내는 양의 정수 n이 주어진다. 각 테스트 케이스는 한 줄에 공백으로 구분된 두 정수 t($1 \le t \le 10^9$)와 s($1 \le s \le 1000$)로 시작한다. t는 CD의 트랙 수이고, s는 Anya가 듣고 싶어 하는 곡의 수이다. 각 테스트 케이스의 둘째 줄에는 Anya가 듣고 싶은 트랙 번호 s개가 순서대로 공백으로 구분되어 주어진다. 각 번호는 1 이상 t 이하이다.

각 테스트 케이스마다 Anya가 원하는 순서대로 곡이 재생되도록 하는 데 필요한 버튼 최소 횟수를 한 줄에 출력한다.

1번 사례에서 Arup은 트랙 67의 재생이 끝난 뒤 뒤로 버튼을 11번 눌러 57을 준비한다. 그다음 앞으로 버튼을 8번 눌러 57이 끝난 뒤 66이 준비되도록 한다. 66이 끝나면 버튼을 누르지 않아 67이 재생되고, 이어서 뒤로 버튼을 20번 눌러 48에 도달한다. 마지막으로 뒤로 버튼을 34번 눌러 15에 가거나, 앞으로 버튼을 34번 눌러 15에 간다. 따라서 최소 횟수는 11 + 8 + 0 + 20 + 34 = 73이다.

2번 사례에서 Arup은 목록의 연속된 두 곡 사이마다 앞으로 버튼이나 뒤로 버튼을 500,000,000번 눌러야 한다.

3번 사례에서 Arup은 트랙 1이 처음 재생된 뒤 두 번째로 재생되기 전에 뒤로 버튼을 한 번 눌러야 한다.