초대형 팬케이크 절단기

당신은 방금 무한 팬케이크 하우스의 총주방장으로 출근했고, 늘 그렇듯 진행 중인 대참사를 발견했다! 다른 요리사들이 실수로 크기가 모두 같은 거대한 원형 팬케이크들을 만들었다. 이 팬케이크들은 통째로 내놓기에는 너무 커서, 요리사들은 이미 팬케이크를 조각들(이 문제에서는 부채꼴이다)로 자르기 시작했다. 현재 N개의 조각이 있으며, 그중 i번째 조각은 내각(중심각)이 $A_{i}$나노도인 부채꼴이다(나노도는 10^{-9}도이다).

음식을 기다리는 손님이 D명 있다. 각 손님은 다른 모든 손님이 받는 조각과 크기가 같은 조각 하나를 원하지만, 그 크기가 얼마인지는 신경 쓰지 않는다. 그러나 현재 조각들만으로는 이렇게 하는 것이 불가능할 수 있으므로, 방사형으로 한 번 이상 잘라야 할 수도 있다.

한 번 자르면 내각이 X인 기존 조각이 내각이 Y와 X - Y인 새로운 조각 두 개로 바뀐다. 임의의 0 < Y < X에 대해 이렇게 할 수 있으며, 이 값들은 정수일 필요가 없다. 이 새로운 조각 중 하나 또는 둘 모두를 다시 자를 수 있고, 이런 식으로 계속할 수 있다.

손님들에게 주지 않는 조각이 크기와 관계없이 하나 이상 남아도 OK다. 이 대참사 때문에 당신도 아침 식사를 놓치고 있으니, 남은 조각은 나중에 먹을 수 있다!

손님들을 만족시키기 위해 필요한 총 절단 횟수의 최솟값을 구한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해, 1 ≤ $A_{i}$ < 360 × $10^{9}$.

테스트 세트 1 (결과 공개)

시간 제한: 20초. 1 ≤ N ≤ 300. 2 ≤ D ≤ 3.

테스트 세트 2 (결과 공개)

시간 제한: 20초. 1 ≤ N ≤ 300. 2 ≤ D ≤ 50.

테스트 세트 3 (결과 비공개)

시간 제한: 60초. 정확히 21개의 경우에 대해, 9000 ≤ N ≤ 10000. 정확히 T-21개의 경우에 대해, 1 ≤ N ≤ 1000. 2 ≤ D ≤ 50.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 현재 가지고 있는 조각의 수와 손님의 수를 나타내는 두 정수 N과 D가 포함된 한 줄로 시작한다. 그다음 줄에는 N개의 정수 $A_{1}$, $A_{2}$, ..., $A_{N}$가 주어지며, 이 중 i번째 정수는 i번째 조각의 내각을 나노도 단위로 나타낸다.

각 테스트 케이스마다 Case #x: y가 포함된 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 필요한 절단 횟수의 최솟값이다.

예제 케이스 #1에서는 처음에 아주 작은 조각 하나만 가지고 있다. 최적의 방법은 한 번 잘라 그 조각을 각이 1/3나노도와 2/3나노도인 두 조각으로 바꾼 다음, 후자의 조각을 다시 잘라 각이 1/3나노도인 조각 두 개로 만드는 것이다.

예제 케이스 #2에서는 이미 크기가 같은 조각 두 개를 가지고 있으므로, 이를 두 손님에게 줄 수 있으며 한 번도 자를 필요가 없다.

예제 케이스 #3에서 최적의 방법은 내각이 8나노도인 조각을 반으로 자르는 것이다. 이 작업을 마치면 내각이 4나노도인 조각이 정확히 3개 있으며, 남는 조각은 없다.

예제 케이스 #4에서는 모든 손님이 반드시 조각 하나를 받아야 한다는 점을 기억해야 한다. 전체 넓이가 같더라도 한 손님에게 "3" 조각을 주고 다른 손님에게 "1" 조각과 "2" 조각을 줄 수는 없다. 이 경우 조건을 만족하려면 적어도 한 번은 잘라야 한다.