타일 자르기 (Large)

엔조는 새로 산 집을 고치고 있다. 가장 까다로운 일은 타일을 딱 필요한 만큼만 사는 것이다. 엔조에게는 정사각형 타일 $N$개가 필요하고, 각 타일의 한 변의 길이는 차례대로 $2^{S_1}, 2^{S_2}, \dots, 2^{S_N}$이다. 같은 크기가 여러 번 나올 수 있다.

가게에서 파는 타일은 한 변이 $M$인 정사각형 한 종류뿐이다. 필요한 타일은 모두 사 온 타일에서 잘라 내야 하고, 엔조는 편하게 작업하려고 자를 때 항상 타일의 변과 평행하게만 자른다. 필요한 타일 하나는 사 온 타일 하나에서 통째로 잘라 내야 하며, 잘라 낸 조각을 이어 붙일 수는 없다.

엔조가 사야 하는 $M \times M$ 타일의 최소 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 필요한 타일의 개수 $N$과 가게에서 파는 타일의 한 변의 길이 $M$으로 시작한다. 그 뒤에 필요한 타일의 크기를 정하는 지수 $S_1, S_2, \dots, S_N$이 차례로 주어진다.

제한

• $1 \le T \le 1000$
• $1 \le N \le 500$
• $1 \le 2^{S_k} \le M \le 2^{31} - 1$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 엔조가 사야 하는 $M \times M$ 타일의 최소 개수이다.