신선한 초콜릿 (라지)

당신은 초콜릿 제조사의 홍보 담당자다. 사장이 인색하다는 인식이 퍼져 회사 이미지가 나빠졌고, 공장 견학과 초콜릿 시식을 무료로 열어 그 인상을 바꾸려고 한다.

기획을 시작하자마자 사장의 평판이 괜히 생긴 것이 아님을 알게 되었다. 사장은 비용을 최소로 줄인다는 조건에서만 무료 초콜릿을 허락했다. 나눠 줄 초콜릿은 한 팩에 $P$조각씩 들어 있다. 견학 그룹마다 새 팩을 뜯고 싶지만, 사장은 앞 그룹에서 남은 조각이 있으면 새 팩을 뜯기 전에 그 조각부터 다음 그룹에게 주라고 못 박았다.

예를 들어 한 팩에 $P = 3$조각이 들어 있고 5명짜리 그룹이 왔다고 하자. 두 팩을 뜯어 한 사람에게 한 조각씩 주면 한 조각이 남는다. 그다음에 6명짜리 그룹이 오면 남은 한 조각을 먼저 주고 두 팩을 더 뜯어 나머지를 주므로 다시 한 조각이 남는다. 이어서 4명짜리 그룹이 둘 오면 앞 그룹은 남은 한 조각과 새로 뜯은 한 팩을 받고, 마지막 4명 그룹은 새로 뜯은 두 팩에서 받는다. 새로 뜯은 팩을 그 자리에서 다 쓸 계획이라도 남은 조각을 모두 쓰기 전에는 새 팩을 뜯을 수 없다.

이 예에서 네 그룹 중 두 그룹(첫 그룹과 마지막 그룹)은 새로 뜯은 팩에서만 초콜릿을 받았다. 나머지 두 그룹은 새 초콜릿과 남은 조각을 섞어 받았다. 남은 조각을 주는 방식이 사장의 인색한 이미지를 지우기에 좋지 않다는 것은 알지만, 기획을 성사시키려면 이 방식을 받아들여야 했다.

$N$개 그룹이 견학을 신청했고 각 그룹은 방문 인원을 알려 주었다. 그룹은 한 번에 하나씩 들어온다. 남은 조각 없이 새 팩에서만 초콜릿을 받는 그룹의 수가 가장 많아지도록 순서를 정하려고 한다. 그룹을 거절할 수 없고, 한 그룹이 초콜릿을 두 번 받을 수도 없으며, 각 그룹의 모든 사람에게 정확히 한 조각씩 주어야 한다.

위 예에서 순서를 5, 6, 4, 4 대신 4, 5, 6, 4로 하면 5명 그룹을 뺀 세 그룹이 새 초콜릿만 받는다. 이 그룹 구성에서는 모든 그룹이 새 초콜릿만 받는 순서가 없으므로 세 그룹이 최선이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 견학 그룹의 수 $N$과 한 팩에 든 초콜릿 조각 수 $P$가 공백으로 구분되어 주어진다. 둘째 줄에는 각 그룹의 인원 $G_1, G_2, \dots, G_N$이 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• 모든 $i$에 대해 $1 \le G_i \le 100$
• $2 \le P \le 4$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 순서를 가장 좋게 정했을 때 남은 조각 없이 새 팩에서만 초콜릿을 받는 그룹의 수다.

최댓값을 만드는 순서는 여러 가지일 수 있다. $P = 3$이고 그룹 인원이 4, 5, 6, 4일 때 6, 5, 4, 4 순서도 새 초콜릿만 받는 그룹을 세 개로 만든다. 이때 새 초콜릿을 받는 그룹이 누구인지는 답과 무관하고, 그런 그룹이 몇 개인지만 센다. 인원은 같고 $P = 2$이면 4, 4, 6, 5처럼 모든 그룹이 새 팩에서만 받게 하는 순서가 있다. 그룹이 모두 1명씩이면 한 팩에서 차례로 나눠 주게 되므로 가장 먼저 들어온 그룹만 새 팩을 받는다.