题目描述

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 需要购买的大瓷砖的数量。

4
1 6 2
2 6 2 2
3 6 2 1 1
7 277 3 8 2 6 1 3 6

Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 2

提示

限制

$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 完成