Description

你所在的城市坐落在壮观的二进制河（Binary river）岸边。河水来自高山上的一些支流。不幸的是，山上的农民需要用这些支流的水来灌溉庄稼。

很久以前，城市与农民达成了一项协议，允许他们在保证河水流动的同时进行耕作：每位农民被允许在一半的时间里为庄稼用水。农民们轮流用一天水，然后让水流入河一天。结果却是一场灾难！因为所有农民的用水时间是同步的，要么全部用水，要么全部不取水，导致河流每隔一天就会干涸，接着第二天又会泛滥。

为了解决这个问题，城市再次与农民协商，让每位农民选择一个介于 $1$ 到 $\mathbf{D}$（包含）之间的 $2$ 的整数次幂（毕竟这是二进制河），并且每经过该天数就切换一次用水状态（即开始或停止取水）。（并不是每个 $1$ 到 $\mathbf{D}$ 之间的 $2$ 的幂都一定被选择，多个农民可以选择相同的数字。$1$ 也算作 $2$ 的幂。）这样做的目的是让整体用水更加均匀，从而减少干旱和洪水的发生。

这一切都发生在很久以前，而你和其他市民最近开始怀疑农民们并没有遵守协议。（你甚至不知道现在有多少农民！）然而，你们唯一掌握的数据是 $\mathbf{N}$ 天的河流水量历史记录。你能判断农民们是否诚实吗？

每条支流的流量为 $1$，主河道的流量等于所有未被农民取水的支流流量之和。（在查看记录之前，你并不知道有多少条支流。）每条支流最多只会被一位农民取水，也可能有些支流从未被农民取水。注意，农民们在城市开始记录水流之前就已经开始了他们的用水周期，但并不能保证他们都是在同一天开始的。

Input Format

输入的第一行是测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行包含两个用空格分隔的整数 $\mathbf{N}$ 和 $\mathbf{D}$。下一行包含 $\mathbf{N}$ 个用空格分隔的整数，第 $\mathrm{i}$ 个整数 $\mathbf{d}_{\mathrm{i}}$ 表示第 $\mathrm{i}$ 天河流的流量。

Output Format

对于每组测试用例，输出一行，格式为 "Case #x: M"，其中 $\mathrm{x}$ 是测试用例编号（从 $1$ 开始），$\mathbf{M}$ 是根据上述模型、与观测到的河流流量一致的最少农民数量。

如果你确定至少有一位农民在活动，但没有任何方式可以用遵守规则的农民来解释给定的输入，则输出 CHEATERS! 代替数字。

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

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

Hint

样例解释

第 1 组数据可以解释为有两条支流，没有农民从中取水。

第 2 组数据可以看作有一条支流，每隔 $4$ 天被取水一次。然而，这组数据的 $\mathbf D$ 是 $2$，所以这位农民违反了协议。

第 3 组数据可以看作有两位农民，各自的取水周期为 $4$ 天。

第 4 组数据可以看作有三位农民，取水周期分别为 $1, 2$ 和 $4$ 天。

数据范围

• $1 \leq \mathbf{T} \leq 50$。
• $\mathbf{D}$ 是 $2$ 的幂。
• $1 \leq \mathbf{D} \leq \operatorname{floor}(\mathbf{N} / 2)$。

小数据集（10 分）

• 时间限制：240 5 秒。
• $1 \leq \mathbf{N} \leq 50$。
• $0 \leq \mathbf{d}_{\mathrm{i}} \leq 5$。

大数据集（17 分）

• 时间限制：480 10 秒。
• $1 \leq \mathbf{N} \leq 5000$。
• $0 \leq \mathbf{d}_{\mathrm{i}} \leq 1000$。

由 ChatGPT 4.1 翻译