더 적은 돈, 더 많은 문제

오늘까지 당신이 사는 나라는 모든 거래에 D개의 서로 다른 양의 정수 액면가를 사용해 왔다. 오늘 한 신하가 가치가 낮은 동전이 가득 든 거대한 자루로 세금을 내려 하자 여왕은 화가 났고, 방금 한 번의 구매에서 어느 한 액면가의 동전도 C개를 초과하여 사용할 수 없다고 명령했다. 예를 들어 C = 2이고 기존 액면가가 1와 5라면, 5 동전 두 개와 1 동전 하나를 사용하여 가치가 11인 물건을 사거나, 5 동전 두 개와 1 동전 두 개를 사용하여 가치가 12인 물건을 사는 것은 가능하지만, 가치가 9 또는 17인 물건을 사는 것은 불가능하다.

여왕의 명령에 직접 이의를 제기할 수는 없지만, 마침 당신은 조폐국을 책임지고 있으므로 새로운 액면가의 동전을 발행할 수 있다. 여왕의 새로운 규칙에 따라 최대 V인 모든 양의 가치를 가진 물건을 구매할 수 있게 하려 한다. (여왕의 명령 전에도 이것이 반드시 가능했던 것은 아니라는 점에 유의한다.) 또한 새 액면가를 가능한 한 적게 도입하려 하며, 기존 액면가와 새 액면가를 합친 최종 집합에는 중복이 없어야 한다.

필요한 새 액면가의 최소 개수는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 각 기존 액면가 ≤ V.

소형 데이터 세트

시간 제한: 240초. C = 1. 1 ≤ D ≤ 5. 1 ≤ V ≤ 30.

대형 데이터 세트

시간 제한: 480초. 1 ≤ C ≤ 100. 1 ≤ D ≤ 100. 1 ≤ V ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 세 값 C, D, V가 있는 한 줄과, 기존 액면가를 오름차순으로 나타내는 공백으로 구분된 D개의 서로 다른 값이 있는 다음 한 줄로 구성된다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 필요한 새 액면가의 최소 개수이다.

케이스 #3과 #4은 소형 데이터 세트의 제한에 속하지 않는다는 점에 유의한다.

케이스 #1에서는 기존 각 액면가의 동전을 최대 한 개씩 사용하여 필요한 모든 가치(1, 2, 3)를 이미 만들 수 있다.

케이스 #2에서는 3 또는 4 중 어느 한 액면가를 추가하는 것으로 충분하다. 어느 것을 선택하든 새 액면가는 하나만 필요하다.

케이스 #3에서 최적해는 액면가 1을 추가하는 것이다.