P16480 [GKS 2014 #A] Cut Tiles

Enzo 正在为他的新家进行装修。最困难的部分就是准确购买所需数量的瓷砖。他需要 $N$ 块不同尺寸的瓷砖。当然，这些瓷砖必须从他购买的大瓷砖上切割出来。所有需要的瓷砖都是正方形，其边长分别为 $2^{S_1}$、$2^{S_2}$、……、$2^{S_N}$。他只能批量购买尺寸为 $M \times M$ 的瓷砖，而且为了方便起见，他决定仅平行于瓷砖的边进行切割。他至少需要购买多少块大瓷砖？

输入的第一行给出测试用例的数量：$\mathbf{T}$。接下来是 $\mathbf{T}$ 行。每行以数字 $\mathbf{N}$ 和 $\mathbf{M}$ 开头，分别表示所需瓷砖的数量和 Enzo 能够购买的大瓷砖的尺寸。随后是 $\mathbf{N}$ 个数字：$\mathbf{S_1}$、$\mathbf{S_2}$、…… $\mathbf{S_N}$，表示所需瓷砖的尺寸。

对于每个测试用例，输出一行形如 `Case #x: y` 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Enzo 需要购买的大瓷砖的数量。

### 限制 $1 \leq 2^{\mathbf{S_k}} \leq \mathbf{M} \leq 2^{31}-1.$ **小数据集（测试集 1 - 可见）** $1 \leq \mathbf{T} \leq 100.$ $1 \leq \mathbf{N} \leq 20.$ **大数据集（测试集 2 - 隐藏）** $1 \leq \mathbf{T} \leq 1000.$ $1 \leq \mathbf{N} \leq 500.$ 翻译由 DeepSeek V4 Pro 完成