외계인의 피아노

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

외계인은 자신이 좋아하는 인간의 노래를 고향으로 가져가고 싶지만, 이를 위해 사용할 수 있는 악기는 음높이가 서로 다른 건반이 4개뿐인 매우 이상한 피아노뿐이다.

외계인은 노래를 외계인 피아노의 건반들로 이루어진 연속열로 적어서 변환한다. 당연히 우리의 노래에는 대개 4개보다 훨씬 많은 음높이가 있으므로, 이 피아노로는 우리의 노래를 완벽하게 변환할 수 없다.

대신 외계인은 다음 규칙에 따라 우리의 노래를 변환하는 것으로 만족하려 한다.

• 우리 노래의 첫 음표는 외계인 피아노의 아무 건반으로나 변환할 수 있다.

• 그 뒤의 모든 음표에 대해,

• 그 음높이가 이전 음표보다 높으면, 이전 음표가 변환된 건반보다 음높이가 높은 건반으로 변환해야 한다.

• 더 낮으면, 이전 음표가 변환된 건반보다 음높이가 낮은 건반으로 변환해야 한다.

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

참고: 음높이가 같은 두 음표가 인접하지 않았다면 같은 건반으로 변환할 필요는 없다.

외계인이 알고 싶은 것은 특정 노래를 변환할 때 규칙을 몇 번이나 어겨야 하는가이다.

더 자세히 설명하기 위해, 우리 노래 중 한 곡에 K개의 음표가 있다고 하자. 첫 음표를 "note 1"(이)라고 하고, 두 번째 음표를 "note 2"(이)라고 하며, 마지막 음표를 "음표 K."라고 한다. 따라서 음표 2은 음표 1의 바로 다음에 온다. 이제 우리 노래에서 음표 2이 음표 1보다 낮지만, 외계인의 노래에서는 음표 2이 변환된 건반과 비교하여 음높이가 같거나 더 낮은 건반으로 변환되었다면, 이를 규칙을 한 번 어긴 것으로 간주한다. 각 테스트 케이스에 대해, 외계인이 그 노래를 변환하면서 반드시 규칙 중 하나를 어겨야 하는 최소 횟수를 구한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $A_{i}$ ≤ $10^{6}$.

테스트 세트 1

시간 제한: 20초. 1 ≤ K ≤ 10.

테스트 세트 2

시간 제한: 40초. 1 ≤ K ≤ $10^{4}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 구성된다. 첫 줄에는 하나의 정수 K가 주어진다. 둘째 줄에는 공백으로 구분된 K개의 정수 $A_{1}$, $A_{2}$ ... $A_{K}$이 주어지며, $A_{i}$은 이 테스트 케이스에서 i번째 음표의 음높이를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 해당 테스트 케이스의 노래를 변환하는 과정에서 외계인이 자신의 규칙을 어겨야 하는 최소 횟수이다.

외계인 피아노의 건반을 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인 우리 노래의 4th 음표가 음높이가 5인 우리 노래의 5th 음표보다 낮지만, A는 D보다 낮은 건반이기 때문이다.