강의 유량

여러분이 사는 도시는 장관을 이루는 이진수 강의 강둑에 자리 잡고 있다. 강물은 산속 아주 높은 곳에서 시작되는 몇몇 지류에서 흘러온다. 안타깝게도 도시에는 산에 살면서 농작물을 위해 지류의 물 일부를 사용해야 하는 농부들이 있다.

오래전, 도시는 강물이 계속 흐르도록 하면서 농부들이 농사를 지을 수 있게 하는 협정을 맺었다. 각 농부는 정확히 절반의 시간 동안 농작물에 물을 사용할 수 있었다. 농부들은 하루 동안 농작물 쪽으로 물길을 돌리고, 다음 하루 동안은 물이 강으로 흘러가도록 두는 일을 번갈아 하기로 했다. 결과는 재앙이었다! 농부들의 물 사용 주기가 동기화되어 모두가 동시에 물길을 돌리거나 돌리지 않았기 때문에, 강은 하루걸러 말라붙고 그다음 날에는 도시에 홍수를 일으켰다.

이 문제를 해결하기 위해 도시는 다시 농부들을 찾아가, 각자 2의 정수 거듭제곱 중에서(어쨌든 이곳은 Binary River이므로) 1 이상 D 이하인 값을 하나 선택하고, 그만큼의 날짜가 지날 때마다 물 사용 상태를 전환하도록(즉, 물을 모으기 시작하거나 중단하도록) 요청했다. (2의 거듭제곱 중 1 이상 D 이하인 모든 값이 반드시 선택된 것은 아니며, 여러 농부가 같은 정수를 선택했을 수도 있다. 1도 2의 거듭제곱으로 간주한다.) 이렇게 하면 전체적인 물 사용량이 더 균일해져 가뭄과 홍수가 발생하는 빈도가 줄어들 것이라는 생각이었다.

이 모든 일은 오래전에 있었으며, 최근 여러분과 다른 시민들은 농부들이 협정을 지키지 않는 것이 아닌지 의심하기 시작했다. (지금 농부가 몇 명인지조차 확실하지 않다!) 하지만 여러분이 가진 자료는 도시를 통과해 흐른 물의 양에 대한 N일간의 기록뿐이다. 농부들이 정직한지 알아낼 수 있는가?

각 지류의 유량은 1이며, 본류의 유량은 농사를 위해 물길이 전환되지 않은 모든 지류의 유량을 합한 값이다. (기록을 살펴보기 전에는 지류가 몇 개인지 알 수 없다.) 각 지류의 물길을 전환하는 농부는 최대 1명이지만, 어떤 농부도 절대 물길을 전환하지 않는 지류가 있을 수도 있다. 농부들은 도시가 유량을 기록하기 훨씬 전부터 물길 전환 주기를 시작했지만, 모두가 같은 날에 시작했다는 보장은 없다는 점에 유의하라.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 50. D는 2의 거듭제곱이다. 1 ≤ D ≤ floor(N / 2).

작은 데이터 세트

시간 제한: 240초. 1 ≤ N ≤ 50. 0 ≤ $d_{i}$ ≤ 5.

큰 데이터 세트

시간 제한: 480초. 1 ≤ N ≤ 5000. 0 ≤ $d_{i}$ ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 N과 D가 있는 줄로 시작한다. 다음 줄에는 공백으로 구분된 N개의 정수가 주어지며, i번째 정수 $d_{i}$는 i번째 날의 강 유량을 나타낸다.

각 테스트 케이스마다 "Case #x: M"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), M은 설명된 모델에 따라 지류의 물길을 전환하면서 관측된 강의 유량과 일치할 수 있는 농부 수의 최솟값이다.

적어도 한 명의 농부가 활동하고 있다고 확신하지만, 주어진 입력을 농부들이 규칙을 준수한 것으로 설명할 방법이 없다면 숫자 대신 CHEATERS!를 출력한다.

설명

케이스 #1은 어떤 농부도 물을 끌어다 쓰지 않는 두 지류가 있는 경우와 일치한다.

케이스 #2은 4일마다 물길이 전환되는 하나의 지류일 수 있다. 하지만 이 경우 D는 2이므로 이 농부는 협정을 어기고 있다.

케이스 #3은 각자의 물길 전환 주기가 4일인 두 농부가 있는 경우일 수 있다.

케이스 #4은 물길 전환 주기가 각각 1일, 2일, 4일인 세 농부가 있는 경우일 수 있다.