가장 가까운 선택

당신은 평생 먹을 수 있는 팬케이크를 상품으로 주는 경품 추첨에 참가하려 한다. 이미 $\mathbf{N}$장의 추첨권이 판매되었다. 각 추첨권에는 $1$ 이상 $\mathbf{K}$ 이하의 정수 하나가 적혀 있다. 서로 다른 추첨권에 같은 정수가 적혀 있어도 된다. 당신은 이미 판매된 모든 추첨권에 어떤 수들이 적혀 있는지 정확히 알고 있으며, 추첨권 두 장을 구매하여 당첨 확률을 최대화하고자 한다. 두 추첨권에는 같은 정수를 적을 수도 있다. 두 추첨권에 적을 정수는 각각 $1$ 이상 $\mathbf{K}$ 이하에서 선택할 수 있다.

당신이 마지막 손님임을 알고 있으므로, 당신이 추첨권을 구매한 뒤에는 추첨권을 더 구매하는 사람이 없다. 그다음 $1$ 이상 $\mathbf{K}$ 이하의 정수 $c$를 균등한 확률로 무작위 선택한다. 당신의 추첨권 중 하나가 다른 모든 추첨권보다 $c$에 엄격히 더 가깝거나, 당신의 두 추첨권이 $c$에서 같은 거리에 있으면서 다른 모든 추첨권보다 엄격히 더 가까우면 경품 추첨에 당첨된다. 그렇지 않으면 당첨되지 않는다.

지금까지 구매된 $\mathbf{N}$장의 추첨권에 적힌 정수들이 주어질 때, 두 추첨권에 적을 정수를 최적으로 선택하여 달성할 수 있는 최대 당첨 확률은 얼마인가?

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 30$. 모든 $i$에 대해 $1 \le \mathbf{P_i} \le \mathbf{K}$.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{K} \le 30$.

테스트 세트 2 (Visible Verdict)

$1 \le \mathbf{K} \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{K}$가 주어지며, 각각 이미 판매된 추첨권의 수와 선택할 수 있는 정수 범위의 한계를 나타낸다. 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{P_1}, \mathbf{P_2}, \dots, \mathbf{P_N}$가 주어지며, 이미 구매된 추첨권들에 적힌 정수를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, $y$는 추첨권을 최적으로 선택했을 때 달성할 수 있는 최대 당첨 확률이다.

$y$가 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고한다.

예제 케이스 #1에서는 정수 $4$과 $8$이 적힌 추첨권을 구매할 수 있으며, 그러면 $4, 5, 8, 9$ 또는 $10$가 선택될 때 당첨되어 당첨 확률 $5/10 = 0.5$를 얻는다. 정수 $6$과 $8$가 적힌 추첨권을 구매해도 당첨 확률 $0.5$를 얻지만, 어떤 조합으로도 이보다 높은 확률을 얻을 수 없다.

예제 케이스 #2에서는 $6$와 $8$가 가능한 최적의 추첨권 한 쌍이며, $c$이 $6, 8, 9$ 또는 $10$ 중 하나일 때 당첨된다. 추첨권에 적힌 정수들이 반드시 정렬된 순서로 주어지는 것은 아니라는 점에 유의한다.

예제 케이스 #3에서는 가능한 모든 $c$이 이미 구매된 추첨권에서 거리 $0$만큼 떨어져 있으므로, 어떻게 선택하더라도 당첨될 수 없다.

예제 케이스 #4에서는 추첨권 중 적어도 하나에 $3$을 선택하면 $c = 3$에서 당첨되어 당첨 확률 $1/4 = 0.25$를 얻는다. $c$이 다른 어떤 정수일 때도 당첨될 방법이 없으므로, 이것이 달성할 수 있는 최선이다.