창고

Advanced Cargo Movement, Ltd.는 다양한 종류의 물품을 보관하는 큰 창고를 운영한다. 이 창고에는 화물을 실을 수 있는 적재구역(bay)이 제한된 개수만큼 있다. 매일 트럭들이 적재구역으로 와서 화물을 싣고(각 트럭은 정확히 한 종류의 물품만 싣는다) 상점으로 떠난다. 적재를 빠르게 하기 위해 창고 관리인은 미리 물품을 적재구역으로 옮겨 둔다. 실제로 실릴 화물의 양을 미리 정확히 알 수 없으므로, 관리인은 필요한 양보다 많은 물품을 준비하고 남은 물품은 나중에 창고로 되돌린다. 따라서 어떤 적재구역에 다음으로 오는 트럭이 이전 트럭과 같은 종류의 물품을 싣는다면, 불필요하게 화물을 옮기지 않아도 되어 유리하다. 트럭의 적재 용량은 적재구역의 용량보다 훨씬 작으므로, 같은 종류의 물품을 원하는 트럭이라면 몇 대가 오더라도 하나의 적재구역에서 다시 채우지 않고 처리할 수 있다.

여러분의 임무는 어떤 종류의 물품을 어떤 적재구역에 준비할지를 정하여, 관리인이 물품을 창고로 되돌리는 횟수를 최대한 적게 만드는 것이다. 매일 시작 시점에는 어떤 적재구역에도 물품이 준비되어 있지 않다. 하루가 끝났을 때 적재구역에 남아 있는 물품은 이동 횟수에 포함하지 않는다.

입력의 첫 줄에는 풀어야 할 테스트 케이스의 수가 주어진다.

각 테스트 케이스는 공백 하나로 구분된 세 정수 $B$, $G$, $N$ ($1 \le B \le 1000$, $1 \le G \le 1000000$, $1 \le N \le 1000000$)이 있는 줄로 시작한다. $B$는 창고의 적재구역 수, $G$는 보관되는 물품 종류의 수, $N$은 창고로 오는 트럭의 수이다. 이어서 $N$개의 줄이 주어지며, $i$번째 줄에는 $i$번째 트럭이 싣고자 하는 물품의 종류 $t_i$ ($1 \le t_i \le G$)가 도착 순서대로 주어진다.

어떤 트럭이 도착했을 때 그 트럭이 원하는 종류의 물품이 어떤 적재구역에도 준비되어 있지 않다면, 트럭을 처리하기 전에 그 종류의 물품을 어떤 적재구역으로 옮겨야 한다. 이 작업을 LOAD 동작 한 번으로 세며, 이때 그 적재구역에 원래 있던 물품은 창고로 되돌려진다. 원하는 종류가 이미 어떤 적재구역에 준비되어 있다면 아무 작업도 필요 없다. 트럭은 도착 순서대로 한 번에 한 대씩 처리한다.

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

Case X: M

여기서 X는 테스트 케이스 번호(1부터 시작)이고, M은 해당 테스트 케이스의 모든 트럭을 처리하는 데 필요한 LOAD 동작의 최소 횟수이다.