Chef is the leader of Chef's Earth Defense Organization, and his mission is to counter aliens which are threatening the earth. According to information gathered by the organization, there are $N$ alien spaceships (numbered $1$ through $N$) planning to invade the earth. The $i$-th spaceship will appear on the radar at time $C_i$. Each spaceship needs $D$ time to reach earth once it appears on the radar. 
Chef's organization owns a huge laser cannon which can destroy one spaceship in one shot. However, once the cannon is used once it needs some amount of cool-down time in order to be used again (first shot doesn't require cool-down time before it is used). This cool-down time, however, is configurable. It has to be set before the first shot, and cannot be changed after that. If Chef sets a lower cool-down time, that would increase the energy consumed by the cannon, and vice-versa - the higher the cool-down time, the lower the energy consumed.
This might be a long battle, and Chef wants to use as little energy as possible. So Chef wants to maximize the cool-down time while still being able to destroy all spaceships before any of them arrive on earth. In particular, the $i$-th spaceship should be shot between the times $C_i$ and $C_i + D$ (both end points inclusive).

-----Input:-----
- The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two integers $N$ and $D$. 
- The second line contains $N$ space-separated integers $C_1, C_2, \ldots, C_N$.

-----Output:-----
For each test case, print a single line containing one real number― the maximum cool-down time possible. Your answer will be considered correct if the absolute or relative error of the answer does not exceed $10^{-6}$.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^5$
- $1 \leq C_i \leq 10^9$ for each valid $i$
- $1 \leq D \leq 10^9$
- The sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points): 
- $N \le 1,000$
- the sum of $N$ over all test cases does not exceed $10,000$
Subtask #2 (50 points): Original constraints

-----Sample Input:-----
2
3 2
3 2 3
2 1
5 6

-----Sample Output:-----
1.5000000000
2.0000000000

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def binary_search(arr, x):\n arr.sort()\n low = 0\n high = len(arr) - 1\n mid = 0\n while low <= high:\n\n  mid = low + (high-low)//2\n  if arr[mid] < x:\n   low = mid + 1\n  elif arr[mid] > x:\n   high = mid - 1\n  else:\n   return mid\n return -1\ndef ternary_search(l, r, key, ar):\n if (r >= l):\n  mid1 = l + (r - l) // 3\n  mid2 = r - (r - l) // 3\n  if (ar[mid1] == key):\n   return mid1\n  if (ar[mid2] == key):\n   return mid2\n  if (key < ar[mid1]):\n   return ternary_search(l, mid1 - 1, key, ar)\n  elif (key > ar[mid2]):\n   return ternary_search(mid2 + 1, r, key, ar)\n  else:\n   return ternary_search(mid1 + 1,\n         mid2 - 1, key, ar)\n return -1\ndef cheaker(c,d,val,n):\n st = c[0]\n for i in range(1,n):\n  if st+val < c[i]:\n   st = c[i]\n  elif st+val > c[i]+d:\n   return False\n  else:\n   st += val\n return True\n\ndef binary_search_answer(low,high,d,a,n,de):\n x=1\n p=0\n while(p!=d):\n  while((high - low )> x):\n   mid = (high+low)/2\n   if cheaker(a,de,mid,n):\n    low= mid\n   else:\n    high = mid\n  x/=10\n  p+=1\n return low\ndef __starting_point():\n for i in range(int(input())):\n  n,d= list(map(int,input().split()))\n  a=[int(X) for X in input().split()]\n  a.sort()\n  print(round(binary_search_answer(0,2*(10**9),7,a,n,d),10))\n# cook your dish here\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14217