你居住的城市坐落在壮观的二进制河（Binary river）岸边。河水来自山上的几条支流。不幸的是，住在山上的农民需要利用支流中的部分水来灌溉农作物。

很久以前，城市与农民达成了一项协议，允许他们在保持河流流动的同时进行耕作：每位农民被允许在正好一半的时间里使用支流的水。农民们交替地进行灌溉：一天引水灌溉，一天让水流入河流。结果却是一场灾难！由于农民们的用水行为是同步的，每个人要么同时引水，要么同时不引水，导致河流每隔一天就会干涸，而第二天又会淹没城市。

为了解决这个问题，城市重新与农民协商，要求每位农民选择一个 $1$ 到 $D$ 之间的整数次幂（毕竟这是二进制河）（包含 $1$ 和 $D$），并在每经过该天数后切换一次用水状态（开始或停止引水）。（并非 $1$ 到 $D$ 之间的每个 $2$ 的幂都一定会被选中，且多位农民可能选择了相同的整数。$1$ 也被视为 $2$ 的幂。）这样做的初衷是使整体用水更加均匀，从而减少干旱和洪涝的频率。

这一切发生在很久以前，你和其他市民最近开始怀疑农民们并没有遵守协议。（你甚至不确定现在有多少位农民！）然而，你手中仅有的数据是 $N$ 天的河流流量历史记录。你能判断农民们是否诚实吗？

每条支流的流量为 $1$，主河道的流量是所有未被用于灌溉的支流流量之和。（在查看记录之前，你不知道总共有多少条支流。）每条支流最多被一位农民引水，但也可能存在没有任何农民引水的支流。注意，农民们开始引水循环的时间远早于城市开始记录流量的时间，但不能保证他们都在同一天开始。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个空格分隔的整数 $N$ 和 $D$。下一行包含 $N$ 个空格分隔的整数，其中第 $i$ 个整数 $d_i$ 表示第 $i$ 天的河流流量。

输出格式

对于每个用例，输出一行 "Case #x: $M$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$M$ 是根据所述模型，在与观测到的河流流量一致的前提下，可能引水的农民的最少数量。

如果你确定至少有一位农民在活动，但提供的输入无法用遵守规则的农民来解释，则输出 CHEATERS! 而不是数字。

数据范围

内存限制：1 GB。

$1 \le T \le 50$。

$D$ 将是 $2$ 的幂。

$1 \le D \le \lfloor N / 2 \rfloor$。

小数据（10 分）

时间限制：10 秒。

$1 \le N \le 50$。

$0 \le d_i \le 5$。

大数据（17 分）

时间限制：20 秒。

$1 \le N \le 5000$。

$0 \le d_i \le 1000$。

样例

样例输入 1

4
5 2
2 2 2 2 2
6 2
1 1 1 0 0 0
8 4
2 1 1 0 0 1 1 2
8 4
0 1 1 3 1 2 2 2

样例输出 1

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

说明

Case #1 与两条没有农民引水的支流情况一致。

Case #2 可能是一位农民每 4 天引水一次。然而，本例中 $D$ 为 2，因此该农民违反了协议。

Case #3 可能是有两位农民，每人的引水周期均为 4 天。

Case #4 可能是有三位农民，引水周期分别为 1、2 和 4 天。