타일 자르기

Enzo는 새집을 수리하고 있다. 가장 어려운 부분은 정확히 필요한 수만큼 타일을 사는 것이다. 그는 서로 다른 크기의 타일 N개를 원한다. 물론 이 타일들은 그가 산 타일에서 잘라 내야 한다. 필요한 모든 타일은 정사각형이다. 타일의 한 변의 길이는 2^{$S_{1}$}, 2^{$S_{2}$}, ..., 2^{$S_{N}$}이다. 그는 크기가 M*M인 타일만 여러 장 살 수 있으며, 편의를 위해 타일의 변과 평행하게만 자르기로 한다. 그는 타일을 몇 장 사야 하는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ 2^{$S_{k}$} ≤ M ≤ $2^{31}$-1.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 100. 1 ≤ N ≤ 20.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 1000. 1 ≤ N ≤ 500.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄은 필요한 타일의 수와 Enzo가 살 수 있는 큰 타일의 크기를 나타내는 N과 M으로 시작한다. 이어서 필요한 타일의 크기를 나타내는 N개의 수 $S_{1}$, $S_{2}$, ... $S_{N}$이 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Enzo가 사야 하는 큰 타일의 수이다.