Moogle Maps

Sunyoung is building a fantastic map app called Moogle Maps, which will ship on the Maple mPhone. The app can point to the location of a street address such as "Main Street 13". However, the mPhone's storage is limited, so Sunyoung has to reduce the amount of stored data.

She realized she does not need to store the exact location of every address. Instead, she stores the exact location of only some addresses and estimates the rest with linear interpolation. She wants to choose which addresses to store so that the average error between the true location and the interpolated location is minimized.

The road can be modeled as a single straight line, and the locations of the first and the last house are always stored.

If the location $x_i$ of the house with address $i$ and the location $x_j$ of the house with address $j$ are stored while the houses in between are not, then the location of the house with address $k$ ($i < k < j$) is estimated as

$$x_i + (x_j - x_i) \cdot \frac{k - i}{j - i}$$

The error of a house whose exact location is stored is $0$.

The first line contains the number of test cases $t$. ($1 \le t \le 50$)

Each test case consists of two lines. The first line contains the number of houses $h$ and the number of locations that can be stored $c$. ($2 \le h \le 200$, $2 \le c \le h$) The second line contains the location of each house in address order. Each location is an integer in $[0, 1000000]$.

For each test case, print the minimum average error achievable by storing $c$ of the $h$ house locations. Print the value to exactly four decimal places, rounding the fifth decimal place half up (0.5 and above rounds up).