카드 게임

Bob은 카드놀이를 좋아한다. Bob의 생일 파티에서 가장 친한 친구 Alice가 카드 한 세트를 선물했다.

카드는 N장이고 각 카드에는 정수가 하나 적혀 있다. Bob은 카드를 책상 위에 왼쪽에서 오른쪽으로 놓고 그중 일부를 버리려고 한다. 카드를 버리기 전에 Bob은 수 K를 하나 선택한다. 매번 Bob은 항상 인접한 카드 3장을 골라 버리며, 각 카드에 적힌 수가 왼쪽부터 a, b, c라고 가정한다. Bob은 다음을 보장한다.

c - b = b - a = K

Bob은 마지막에 남길 수 있는 카드 수의 최솟값을 알고 싶어 한다. 버릴 카드를 선택할 수 있는 경우가 생길 때마다, Bob은 마지막에 남는 카드 수가 가장 적어지도록 카드를 선택한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

1 ≤ T ≤ 100. 1 ≤ $a_{i}$ ≤ $10^{6}$(1 ≤ i ≤ N). 1 ≤ N ≤ 100.

작은 데이터 세트(테스트 세트 1 - 공개)

K = 0.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ K ≤ $10^{6}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 각 테스트 케이스의 첫 줄에는 카드 수 N과 Bob이 선택한 수 K, 두 정수가 주어진다. 둘째 줄에는 카드에 적힌 수를 왼쪽부터 나타내는 N개의 정수 $a_{1}$, $a_{2}$, ..., $a_{N}$이 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 Bob이 버릴 수 있는 모든 카드를 버린 뒤 남길 수 있는 카드 수의 최솟값이다.