이야기 하나 들려줄게

이야기는 이렇다...

아주, 아주 오래전, 공정왕 Tyrone에게는 4명의 대신이 있었다. 첫 번째 대신(왕의 수석 고문)은 매주 금화 7개를 받았다. 두 번째 대신은 매주 금화 4개를 받았다. 세 번째와 네 번째 대신은 각각 매주 금화 6개를 받았다. 안타깝게도 어느 날 Tyrone은 실수로 복사기에 대신 보수 목록을 두고 왔고, 그 목록은 Kingdom Times 신문의 일면에 실렸다. 그러자 두 번째 대신은 자신보다 지위가 낮은 세 번째 대신보다 자신의 봉급이 적다는 사실에 화가 나 왕과 면담을 요청했다.

공정왕 Tyrone은 세 번째 대신을 해고하는 것 외에는 다른 해결책이 없다고 생각했다. 왕의 생각에는 세 번째 대신의 봉급을 낮추거나, 두 번째 대신의 봉급을 올리거나, 직함을 바꾸는 방법이 모두 불공정한 해결책이었기 때문이다. 우리가 감히 Tyrone 왕에게 의문을 제기할 수 있겠는가? 물론 세 번째 대신을 해고해도 문제는 해결되지 않았다. 두 번째 대신은 여전히 자신의 봉급이 네 번째 대신보다 적었기 때문에 계속 불평했다. 그래서 Tyrone 왕은 네 번째 대신도 해고했다. 이제 남은 두 대신 중 누구도 불평하지 않았고, 모두가 오래오래 행복하게 살았다.

...잠깐만. 이야기를 잘못했네. 미안하다. 예전처럼 기억력이 좋지 않다. 잠시만... 그래. 공정왕 Tyrone. 네 명의 대신. 각각 7, 4, 6, 6을 받았다. 아, 맞다. 결말은 이랬다...

두 번째 대신이 불공정하다고 불평하자 Tyrone 왕은 첫 번째 대신을 해고했다. 첫 번째 대신은 어떤 식으로도 관련되지 않았으니 다소 가혹했다고 말하는 사람도 있겠지만, Tyrone 왕에게 의문을 제기해서는 안 된다. 당연히 두 번째 대신은 여전히 불평했고, 그래서 Tyrone 왕은 그를 간단히 해고했다. 남은 두 대신은 각각 자신보다 아래에 있는 어느 대신보다도 적지 않은 봉급을 받고 있었으므로 아무도 불평하지 않았다. 그리고 모두가 오래오래 행복하게 살았다.

훨씬 낫군... 아마도. 그런가? 이제는 더 이상 확신할 수 없다. 대신이 N명 있었다는 것과 그들의 봉급은 확실히 기억한다. 또한 어떤 대신의 봉급이 자신보다 아래에 있는 대신의 봉급보다 적을 때마다 누군가가 불평했고, 어떤 대신 한 명이 해고되었다는 것도 알고 있다. 하지만 문제와 조금이라도 관련이 있는지와 관계없이 어느 대신이든 해고될 수 있었다. 모든 봉급이 비증가 순서가 되어 아무도 불평하지 않을 때까지 대신들은 계속 해고되었다. 그 시점에 해고가 멈췄다. 하지만 대신들이 어떤 순서로 해고되었는지는 기억하지 못한다.

내 이야기를 바로잡도록 도와줄 수 있는가? 아니면 적어도 내가 서로 다른 이야기를 몇 가지나 들려줄 수 있었는지 알려 달라. 해고된 대신들의 순서가 같지 않다면 두 이야기는 서로 다르다.

제한

메모리 제한: 1GB. 각 봉급은 양수이며 최대 10000이다.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. 1 ≤ T ≤ 100. 1 ≤ N ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ T ≤ 20. 테스트 케이스의 80%에 대해, 1 ≤ N ≤ 2000. 모든 테스트 케이스에 대해, 1 ≤ N ≤ 8000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 정수 N이 주어지고, 두 번째 줄에는 첫 번째 대신부터 N번째 대신까지의 봉급을 순서대로 나타내는, 공백으로 구분된 N개의 정수가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호로 1부터 시작하며, y는 내가 들려줄 수 있었던 이야기의 수를 10007로 나눈 나머지이다.