你刚刚入职“无限煎饼屋”担任主厨，像往常一样，你发现厨房里乱成了一团！其他厨师不小心制作了一些巨大的圆形煎饼，它们的大小都相同。这些煎饼太大了，无法直接整块供应，所以他们已经开始将其切成薄片（在本题中，薄片为扇形）。你目前有 $N$ 片薄片，第 $i$ 片是一个圆心角为 $A_i$ 纳度的扇形（1 纳度为 $10^{-9}$ 度）。

你有 $D$ 位食客在等待食物。每位食客都想要一片与其他食客大小完全相同的薄片，尽管他们并不在意具体的大小是多少。但使用现有的薄片可能无法做到这一点，因此你可能需要进行一次或多次径向切割。

一次切割可以将一个圆心角为 $X$ 的现有薄片变成两个圆心角分别为 $Y$ 和 $X - Y$ 的新薄片。对于任何 $0 < Y < X$，你都可以进行此操作，且这些值不需要是整数。你可以对这两个新薄片中的任意一个（或两个）进行进一步切割，以此类推。

允许存在一个或多个不分给食客的剩余薄片（任意大小）；你可以在之后吃掉它们，因为这场混乱让你错过了自己的早餐！

请确定为了满足食客需求，你需要进行的最少切割总次数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $D$：你目前拥有的薄片数量和食客数量。接下来的一行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，其中第 $i$ 个数表示第 $i$ 片薄片的圆心角（单位为纳度）。

输出格式

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

数据范围

$1 \le T \le 100$。 $1 \le A_i < 360 \times 10^9$，对于所有 $i$。

样例

样例输入 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/3$ 纳度和 $2/3$ 纳度的两片薄片，然后进一步将后者切成两片圆心角为 $1/3$ 纳度的薄片。

在样例 2 中，你已经有了两片大小相同的薄片，因此你可以直接将它们分给两位食客，无需进行任何切割。

在样例 3 中，最优解是将圆心角为 8 纳度的薄片对半切开。操作后，你恰好拥有 3 片圆心角为 4 纳度的薄片，没有剩余。

在样例 4 中，请记住每位食客必须收到一片薄片。你不能给一位食客“3”号薄片，而给另一位食客“1”号和“2”号薄片，即使总面积相同也不行。在这种情况下，你必须至少进行一次切割才能满足要求。