강물의 유량 (큰 입력)

도시는 이진 강(Binary River) 강가에 있다. 강물은 산속에서 시작하는 지류에서 흘러온다. 산에는 농부가 살고, 농사를 지으려고 지류의 물을 끌어다 쓴다.

오래전에 도시와 농부들은 각 농부가 전체 기간의 정확히 절반만 물을 쓰기로 합의했다. 농부들은 하루 동안 물을 끌어 쓰고 다음 하루는 그대로 흘려보냈다. 그런데 모두가 같은 날에 물을 끌어 썼기 때문에 강은 하루걸러 말랐고, 그 다음 날에는 도시에 물이 넘쳤다.

그래서 도시는 농부들에게 1 이상 $D$ 이하인 2의 거듭제곱을 하나씩 고르고, 그 일수가 지날 때마다 물 사용을 전환(끌어 쓰기 시작하거나 멈추기)하라고 요청했다. 1 이상 $D$ 이하인 2의 거듭제곱을 누군가는 반드시 골라야 하는 것은 아니고, 여러 농부가 같은 수를 골라도 된다. 1도 2의 거듭제곱이다.

합의한 지 오래되어 시민들은 농부들이 약속을 지키지 않는다고 의심한다. 지금 농부가 몇 명인지조차 모른다. 남은 증거는 도시를 지나는 강물의 유량을 연속한 $N$일 동안 기록한 값뿐이다.

지류는 각각 유량이 1이고, 어느 날 본류의 유량은 그날 물을 빼앗기지 않은 지류의 개수다. 지류가 몇 개인지는 알 수 없다. 지류 하나에서 물을 끌어 쓰는 농부는 많아야 한 명이고, 아무도 물을 끌어 쓰지 않는 지류가 있어도 된다. 따라서 농부 수는 지류 수를 넘지 않는다. 농부들은 기록이 시작되기 훨씬 전부터 자기 주기를 돌리고 있었고, 모두가 같은 날에 시작한 것도 아니다.

기록이 약속을 지키는 농부들에게서 나올 수 있는지 판단하라.

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

제한

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

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

지류 수를 어떻게 잡아도, 규칙을 지키는 농부를 어떻게 배치해도 기록된 유량이 나오지 않으면 숫자 대신 CHEATERS!를 출력한다.

첫 번째 예제의 네 경우는 다음과 같이 설명된다.

• 1번: 지류가 두 개이고 아무도 물을 끌어 쓰지 않는다.
• 2번: 지류 하나에서 4일마다 전환하며 물을 끌어 쓰면 기록과 맞는다. 그런데 이 경우 $D$가 2라서 그 농부는 약속을 어겼다.
• 3번: 4일마다 전환하는 농부 두 명이면 기록과 맞는다.
• 4번: 각각 1일, 2일, 4일마다 전환하는 농부 세 명이면 기록과 맞는다.