Cut Tiles (Large)

Enzo is renovating the house he just bought. The hardest part is buying exactly the right number of tiles. He needs $N$ square tiles whose side lengths are $2^{S_1}, 2^{S_2}, \dots, 2^{S_N}$ in that order. The same size may appear more than once.

The store sells one product only, a square tile of side $M$. Every tile Enzo needs has to be cut out of a tile he bought, and to keep the work simple he only makes cuts parallel to the sides of the tile he is cutting. Each required tile comes out of a single purchased tile in one piece, and cut pieces cannot be joined together.

Find the smallest number of $M \times M$ tiles Enzo has to buy.

The first line contains the number of test cases $T$. Each of the next $T$ lines holds one test case. A line starts with the number of required tiles $N$ and the side length $M$ of the tiles on sale. Then come the exponents $S_1, S_2, \dots, S_N$ that give the sizes of the required tiles.

Limits

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

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the smallest number of $M \times M$ tiles Enzo has to buy.