적은 돈, 많은 문제 (Large)

당신이 사는 나라는 오늘까지 서로 다른 양의 정수 액면가 $D$종의 동전으로 모든 거래를 해 왔다. 오늘 한 백성이 잔돈을 자루째 들고 와 세금을 내려 하자 여왕이 화를 냈고, 한 번의 구매에 같은 액면가의 동전을 $C$개까지만 쓸 수 있다는 칙령을 내렸다. 예를 들어 $C = 2$이고 기존 액면가가 1과 5라면, 5짜리 두 개와 1짜리 하나로 값이 11인 물건을 살 수 있고 5짜리 두 개와 1짜리 두 개로 값이 12인 물건을 살 수 있지만, 값이 9인 물건이나 값이 17인 물건은 살 수 없다.

칙령을 정면으로 거스를 수는 없다. 그러나 당신은 조폐국을 맡고 있으므로 새 액면가의 동전을 발행할 수 있다. 목표는 값이 $V$ 이하인 모든 양의 정수 값의 물건을 새 규칙 아래에서 살 수 있게 만드는 것이다. (칙령 이전에도 불가능했을 수 있다.) 새로 만드는 액면가는 되도록 적어야 하고, 기존 액면가와 새 액면가를 합친 최종 집합에는 같은 값이 두 번 들어가면 안 된다.

새로 발행해야 하는 액면가의 최소 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 세 정수 $C$, $D$, $V$가 있는 줄과, 기존 액면가 $D$개가 오름차순으로 공백으로 구분되어 주어지는 줄로 이루어진다. 기존 액면가는 모두 서로 다르다.

제한

• $1 \le T \le 100$
• $1 \le C \le 100$
• $1 \le D \le 100$
• $1 \le V \le 10^9$
• 기존 액면가는 모두 $V$ 이하의 양의 정수이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 새로 발행해야 하는 액면가의 최소 개수이다.

예제의 첫 번째 테스트 케이스에서는 기존 액면가 1과 2를 한 개씩만 써도 필요한 값 1, 2, 3을 모두 만들 수 있다.

두 번째 테스트 케이스에서는 액면가 3이나 액면가 4 중 하나만 추가하면 충분하므로, 어느 쪽을 고르든 새 액면가는 하나면 된다.

세 번째 테스트 케이스에서는 액면가 1을 추가하는 것이 최적이다.