외계인 피아노

외계인이 막 지구에 착륙했고, 우리 음악을 아주 좋아한다. 우리에게는 다행이다.

외계인은 좋아하는 인간의 노래를 집으로 가져가고 싶지만, 그걸 연주할 악기가 아주 이상하다. 서로 다른 음높이를 가진 건반이 4개뿐인 피아노다.

외계인은 노래를 외계인 피아노의 건반 나열로 적어서 변환한다. 이 피아노는 우리 노래를 완전히 변환할 수 없다. 우리 노래는 보통 음높이가 4개보다 훨씬 많기 때문이다.

외계인은 다음 규칙으로 우리 노래를 변환하는 데 만족하기로 한다.

• 우리 노래의 첫 음은 외계인 피아노의 어떤 건반으로든 변환할 수 있다.

• 그 뒤의 모든 음에 대해,

  • 음높이가 이전 음보다 높으면, 이전 음의 변환보다 높은 음높이의 건반으로 변환해야 한다.
  • 낮으면, 이전 음의 변환보다 낮은 음높이의 건반으로 변환해야 한다.
  • 정확히 같으면, 이전 음의 변환과 같은 건반으로 변환해야 한다.

참고: 음높이가 같은 두 음이라도 서로 인접해 있지 않으면 같은 건반으로 변환할 필요가 없다.

외계인이 알고 싶은 것은 특정 노래를 변환할 때 규칙을 얼마나 자주 깨야 하는가이다.

자세히 설명하자면, 우리 노래 하나에 K개의 음이 있다고 하자. 첫 음을 "1번 음", 둘째 음을 "2번 음", 마지막 음을 "K번 음"이라고 부른다.

따라서 2번 음은 1번 음 바로 뒤에 온다.

이제 우리 버전의 노래에서 2번 음이 1번 음보다 낮은데, 외계인 버전의 노래에서는 (2번 음의 변환을 기준으로) 같은 음높이거나 더 낮은 음높이의 건반으로 변환되었다면, 규칙을 한 번 깬 것으로 본다.

각 테스트 케이스마다 외계인이 그 노래를 변환하면서 반드시 깨야 하는 규칙 위반 횟수의 최솟값을 구하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그 뒤에 T개의 테스트 케이스가 이어진다.

각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에는 정수 K 하나가 주어진다.

둘째 줄에는 공백으로 구분된 K개의 정수 A1, A2, ..., AK가 주어지며, Ai는 이 테스트 케이스에서 i번째 음의 음높이이다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 그 테스트 케이스에서 외계인이 변환 과정에서 규칙을 깨야 하는 최소 횟수이다.

• 1 ≤ T ≤ 100.
• 1 ≤ Ai ≤ 106.

외계인 피아노의 건반을 A, B, C, D로 표기하며, A가 가장 낮은 음이고 D가 가장 높은 음이다. 예제 1에서 외계인은 우리 노래를 다음 수열로 그대로 대응시킬 수 있다: A B C D C. 이는 다음을 모두 정확히 반영한다.

• 음높이 1인 첫 음은 A로 대응된다.
• 음높이 5인 둘째 음은 건반 B로 대응된다. 5 > 1이고, B는 A보다 높은 건반이다.
• 음높이 100인 셋째 음은 건반 C로 대응된다. 100 > 5이고, C는 B보다 높은 건반이다.
• 음높이 500인 넷째 음은 건반 D로 대응된다. 500 > 100이고, D는 C보다 높은 건반이다.
• 음높이 1인 다섯째 음은 건반 C로 대응된다. 1 < 500이고, C는 D보다 낮은 건반이다.

따라서 규칙은 하나도 깨지지 않는다. 참고: A B C D C만이 유일한 변환 방법은 아니다. A B C D A나 A B C D B도 가능한 변환이다.

예제 2에서 규칙을 1번 깨는 최소 결과를 내는 유일한 변환 수열은 A B C D A B C D이다. 특히 규칙 위반은 음높이 4인 4번째 음이 음높이 5인 5번째 음보다 낮은데, A가 D보다 낮은 건반이라는 점에서 비롯된다.