River Flow (Small)

The city you live in sits on the banks of the Binary river. The water in the river comes from tributary streams that start up in the mountains. Farmers live in those mountains, and they need some of the water in the tributary streams for their crops.

Long ago the city struck a deal with the farmers that let them farm while keeping the river flowing: each farmer was allowed to use the water for her crops exactly half the time. The farmers took turns, diverting water for a day and then letting it run down the river for a day. The result was a disaster. Water usage was synchronized, with every farmer diverting or not diverting on the same day, so the river ran dry every other day and flooded the city on the days in between.

To fix this, the city went back to the farmers and asked each one to choose an integer power of two between $1$ and $D$, inclusive (this is the Binary river after all), and to toggle her water usage, either starting or stopping her diversion, every time that number of days has elapsed. Not every power of two between $1$ and $D$ has to be used, and several farmers may pick the same number. $1$ counts as a power of two. The idea was that water usage would spread out and that droughts and floods would become rarer.

All of this happened a long time ago, and you and the other citizens have recently become suspicious that the farmers are not sticking to the agreement. You do not even know how many farmers there are right now. The only data you have is $N$ days of history of the amount of water flowing through the city. Can you tell whether the farmers are honest?

Each tributary stream has flow $1$, and the flow through the main river is the sum of all the tributary streams that are not being diverted for farming. Before looking at the records you do not know how many tributary streams there are. At most one farmer diverts water from each tributary stream, and some tributary streams may have no farmer on them at all. The farmers started their diversion cycles long before the city started recording the water flow, and there is no guarantee that they all started on the same day.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing 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 two.
• $1 \le D \le \lfloor N/2 \rfloor$
• $1 \le N \le 50$
• $0 \le d_i \le 5$

For each test case, output 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 observed flow while following the rules above.

If you are sure that at least one farmer is diverting water, but no set of farmers obeying the rules can explain the record, output CHEATERS! instead of a number.

In the sample, the first case is explained by two tributary streams with no farmer drawing from them.

The second case could be a single tributary stream diverted every 4 days, but $D$ is $2$ in that case, so that farmer breaks the agreement.

The third case is explained by two farmers who toggle every 4 days.

The fourth case is explained by three farmers who toggle every 1, 2 and 4 days.