题目描述

当你作为"无限煎饼屋"的主厨刚上班时，又一次发现灾难现场！其他厨师不小心做出了一些巨大的圆形煎饼，且所有煎饼大小相同。这些煎饼太大无法整块供应，于是他们已经开始将煎饼切成扇形切片（在本问题中即为圆形扇形）。你现在有 $\mathbf{N}$ 块切片，其中第 $i$ 块是中心角为 $\mathbf{A}_i$ 纳度（1 纳度 = $10^{-9}$ 度）的扇形。

现在有 $\mathbf{D}$ 位顾客等待用餐。每位顾客需要一块与其他顾客大小完全相同的切片（具体大小不限）。但现有切片可能无法满足需求，因此你可能需要进行若干次径向切割。

一次切割操作可以将一个中心角为 $X$ 的切片分成两个新切片，其中心角分别为 $Y$ 和 $X - Y$。其中 $0 < Y < X$ 且不需要为整数。你可以对这两个新切片继续切割，以此类推。

允许存在任意大小的剩余切片（不供应给顾客）——毕竟这场灾难让你错过了早餐！

请计算满足顾客需求所需的最少切割次数。

输入格式

输入第一行包含测试用例数量 $\mathbf{T}$。随后每个测试用例包含：

• 第一行：两个整数 $\mathbf{N}$（现有切片数）和 $\mathbf{D}$（顾客数）
• 第二行：$\mathbf{N}$ 个整数 $\mathbf{A}_1, \mathbf{A}_2, ..., \mathbf{A}_\mathbf{N}$，表示每块切片的中心角（纳度）

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为所需的最少切割次数。

输入输出样例 #1

输入 #1

4
1 3
1
5 2
10 5 359999999999 123456789 10
2 3
8 4
3 2
1 2 3

输出 #1

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

说明/提示

样例解释

样例 #1：初始只有 1 块极小切片。最优方案是：

1. 第一次切割得到 $1/3$ 纳度和 $2/3$ 纳度的切片
2. 将后者再次切割为两块 $1/3$ 纳度的切片 最终得到 3 块相同切片，共需 2 次切割。

样例 #2：已有两块相同大小的切片可直接供应，无需切割。

样例 #3：最优方案是将 8 纳度的切片对半切割，得到 3 块 4 纳度的切片且无剩余。

样例 #4：注意每位顾客必须获得单块切片。即使 "1+2" 和 "3" 的总面积相同，也不符合要求。此时至少需要进行 1 次切割。

数据范围

• $1 \leq T \leq 100$
• $1 \leq A_i < 360 \times 10^9$（所有 $i$）

测试集 1（10 分，可见判定）

• 时间限制：20 秒
• $1 \leq N \leq 300$
• $2 \leq D \leq 3$

测试集 2（16 分，可见判定）

• 时间限制：20 秒
• $1 \leq N \leq 300$
• $2 \leq D \leq 50$

测试集 3（16 分，隐藏判定）

• 时间限制：60 秒
• 其中 21 个用例满足 $9000 \leq N \leq 10000$
• 其余 $T-21$ 个用例满足 $1 \leq N \leq 1000$
• $2 \leq D \leq 50$