신선한 초콜릿 (스몰)

당신은 초콜릿 제조 회사의 홍보 담당자다. 사장이 인색하다는 인상 탓에 회사 이미지가 나빠졌고, 그 인상을 뒤집으려고 공장 견학과 초콜릿 시식을 무료로 열기로 했다.

일을 시작하고 보니 사장의 평판에는 이유가 있었다. 사장은 비용을 최소로 줄인다는 조건에서만 무료 초콜릿 제공에 동의했다. 나눠 줄 초콜릿은 한 팩에 $P$조각씩 들어 있다. 당신은 견학 그룹마다 새 팩을 열고 싶지만, 사장은 앞 그룹에서 남은 조각이 있으면 새 팩을 열기 전에 그 조각부터 다음 그룹에게 써야 한다고 못 박았다.

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

이 예에서 네 그룹 중 두 그룹(첫 번째와 마지막)은 새로 연 팩에서만 초콜릿을 받았다. 나머지 두 그룹은 새 초콜릿과 남은 조각을 섞어 받았다. 남은 조각을 건네는 방식이 사장의 인색한 이미지를 지우기에 좋지 않다는 것은 알지만, 이 조건을 받아들여야 사장이 행사를 승인했다.

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

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

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

제한

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

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

첫 번째 예제 테스트 케이스는 문제에서 설명한 상황과 같다. 위에서 든 순서 말고 6, 5, 4, 4 같은 순서도 새 초콜릿만 받는 그룹 수를 최대로 만든다. 다만 그때 새 초콜릿을 받는 그룹이 같지는 않다. 가장 좋은 대접을 받는 그룹의 개수만 세고, 그 그룹에 속한 사람의 총수는 세지 않는다.

두 번째 예제 테스트 케이스는 그룹 구성이 첫 번째와 같지만 한 팩에 두 조각이 들어 있다. 이때는 4, 4, 6, 5처럼 모든 그룹이 새 초콜릿만 받는 순서가 여럿 있다.

세 번째 예제 테스트 케이스는 모든 그룹이 한 명씩이고 전부 같은 팩에서 먹는다. 새로 연 팩을 받는 그룹은 가장 먼저 들어온 하나뿐이다.