강의 유량 (Small)

당신이 사는 도시는 이진 강가에 있다. 강물은 산에서 시작하는 여러 지류에서 흘러 내려온다. 산에는 농부들이 살고, 농사를 지으려면 지류의 물을 끌어다 써야 한다.

오래전에 도시는 강이 마르지 않게 하면서 농사도 지을 수 있도록 농부들과 협약을 맺었다. 각 농부는 전체 기간의 정확히 절반만 물을 쓸 수 있다. 농부들은 하루는 물을 끌어 쓰고 하루는 그대로 흘려보내는 식으로 번갈아 물을 썼다. 결과는 나빴다. 모든 농부가 같은 날 물을 끌어 쓰고 같은 날 흘려보냈기 때문에, 강은 하루걸러 말라붙었고 그다음 날에는 도시로 넘쳤다.

도시는 농부들을 다시 찾아가서, 각자 $1$ 이상 $D$ 이하의 2의 거듭제곱을 하나 고르고 그만큼의 날이 지날 때마다 물 사용을 전환하라고, 즉 물을 끌어 쓰기 시작하거나 멈추라고 요청했다. 강 이름이 이진 강이니 그럴 만도 하다. $1$ 이상 $D$ 이하의 2의 거듭제곱이 모두 쓰일 필요는 없고, 여러 농부가 같은 수를 골라도 된다. $1$도 2의 거듭제곱으로 센다. 이렇게 하면 물 사용이 고르게 퍼져서 가뭄과 범람이 줄어들 것이라는 계산이었다.

이 일은 오래전에 있었고, 최근 당신과 다른 시민은 농부들이 협약을 지키지 않는다고 의심하기 시작했다. 지금 농부가 몇 명인지조차 모른다. 가진 자료는 도시를 지나는 물의 양을 $N$일 동안 기록한 것뿐이다. 이 기록만으로 농부들이 정직한지 판단할 수 있는가?

지류 하나의 유량은 $1$이고, 본류의 유량은 농사에 쓰이지 않는 지류의 유량을 모두 더한 값이다. 기록을 보기 전에는 지류가 몇 개인지 모른다. 지류 하나에서 물을 끌어 쓰는 농부는 많아야 한 명이고, 어떤 농부도 물을 끌어 쓰지 않는 지류가 있어도 된다. 농부들은 도시가 유량을 기록하기 훨씬 전부터 물 사용 주기를 시작했고, 모두가 같은 날 시작했다는 보장은 없다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $D$가 공백으로 구분되어 주어진다. 다음 줄에는 $N$개의 정수가 공백으로 구분되어 주어지고, $i$번째 정수 $d_i$는 $i$일째 강의 유량이다.

제한

• $1 \le T \le 50$
• $D$는 2의 거듭제곱이다.
• $1 \le D \le \lfloor N/2 \rfloor$
• $1 \le N \le 50$
• $0 \le d_i \le 5$

각 테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $M$은 위 규칙을 지키면서 관측된 유량을 만들어 낼 수 있는 농부 수의 최솟값이다.

물을 끌어 쓰는 농부가 최소 한 명 있는 것은 확실한데 규칙을 지키는 농부들로는 주어진 기록을 설명할 방법이 없다면, 숫자 대신 CHEATERS!를 출력한다.

예제의 첫 번째 케이스는 농부가 아무도 물을 끌어 쓰지 않는 지류 두 개로 설명된다.

두 번째 케이스는 4일마다 물길을 돌리는 지류 하나로 설명할 수 있지만, 이 케이스의 $D$는 $2$이므로 그 농부는 협약을 어긴 것이다.

세 번째 케이스는 전환 간격이 4일인 농부 두 명으로 설명된다.

네 번째 케이스는 전환 간격이 각각 1일, 2일, 4일인 농부 세 명으로 설명된다.