River Flow (Large)

The city lies on the bank of the Binary River. Its water comes from tributary streams that start high in the mountains. Farmers live in those mountains and take water from the streams for their crops.

Long ago the city and the farmers agreed that each farmer may use the water exactly half of the time. The farmers diverted water for a day and let it run down the river the next day. Because they all diverted on the same days, the river ran dry every other day and flooded the city on the days in between.

So the city asked every farmer to pick one power of 2 between 1 and $D$, inclusive, and to toggle her water usage (start or stop diverting) each time that many days have passed. Not every power of 2 between 1 and $D$ has to be picked by someone, and several farmers may pick the same number. 1 counts as a power of 2.

The agreement is old, and the citizens suspect that the farmers no longer keep it. Nobody even knows how many farmers there are now. The only evidence is a record of the river flow past the city on $N$ consecutive days.

Each tributary stream has flow 1, and the flow of the main river on a day is the number of streams that are not diverted that day. The number of streams is unknown. At most one farmer diverts water from any single stream, and some streams may have no farmer at all, so the number of farmers never exceeds the number of streams. The farmers started their cycles long before the city began recording, and they did not all start on the same day.

Decide whether the record can come from farmers who keep the agreement.

The first line of the input gives the number of test cases $T$. The first line of each test case contains two space separated integers $N$ and $D$. The next line contains $N$ space separated integers, where the $i$-th integer $d_i$ is the river flow on day $i$.

Limits

• $1 \le T \le 50$
• $D$ is a power of 2.
• $1 \le D \le \lfloor N / 2 \rfloor$
• $2 \le N \le 5000$
• $0 \le d_i \le 1000$

For each test case, print one line containing "Case #x: M", where $x$ is the test case number starting from 1 and $M$ is the smallest number of farmers that can produce the recorded flow under the rules above.

If no number of streams and no placement of rule abiding farmers produces the recorded flow, print CHEATERS! in place of the number.

The four cases of the first example are explained as follows.

• Case 1 fits two tributary streams with no farmer drawing from either one.
• Case 2 fits a single stream diverted with a toggle every 4 days. Here $D$ is 2, so that farmer broke the agreement.
• Case 3 fits two farmers who each toggle every 4 days.
• Case 4 fits three farmers who toggle every 1, 2 and 4 days.