With the development of the 325th phase of Wuling Industry, the ecology of the Wuling region has undergone tremendous changes. Nowadays, there are $n$ gates distributed in order along the waterway from Qingbo Village to Wuling City, numbered $1, 2, \dots, n$. Traveling by bamboo raft from gate $i-1$ to gate $i$ takes $t_i$ units of time ($2 \le i \le n$).

Each gate has a periodic traffic restriction: the gate alternates between "open" and "closed" states, with each state lasting for $k$ units of time (i.e., a complete open-closed cycle length is $2k$). When a gate is in the open state, the bamboo raft can pass through instantly (taking zero time); when a gate is in the closed state, the bamboo raft must wait in front of the gate until it switches to the open state to pass.

As an operator of the terminal, Little H, with the help of Yvonne, has infiltrated the central system. He has the highest authority and can set the initial start time of each gate arbitrarily before departure. However, due to the complexity of the waterway environment and uncontrollable delays in the underlying system, Little H's arrival time at the starting point cannot be precisely synchronized with the system. In layman's terms: when Little H arrives exactly at gate 1 at time 0 to prepare for departure, the exact moment of the cycle that gate 1 is in is completely random.

Formally: Each gate has a clock $S_i$ ($S_i \in [0, 2k), S_i \in \mathbb{R}$). Before arriving at gate 1, Little H can arbitrarily set the values of all $S_i$ ($1 \le i \le n$). There exists an uncontrollable global unknown offset $\Delta$ ($\Delta \in \mathbb{R}$) in the system, and $\Delta$ is independently and uniformly distributed in the continuous interval $[0, 2k)$. The clocks flow continuously and uniformly as time passes. At any time $t$ ($t \ge 0, t \in \mathbb{R}$) after departure, the actual clock value of gate $i$ is $T_i(t) = (S_i + \Delta + t) \pmod{2k}$. At time $t$, if $T_i(t) < k$, the gate $i$ is open and passage is allowed; if $T_i(t) \ge k$, the gate $i$ is closed and one must wait.

Now, Little H needs to take a bamboo raft to pass through these $n$ gates in order to reach Wuling City. It is known that he will adopt the most perfect strategy to set all $S_i$ to minimize the total travel time. What is the minimum mathematical expectation of the total time spent (including travel time and all waiting times) from the start at time 0 until Little H successfully passes the last (the $n$-th) gate?

Input

The input contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$) representing the number of test cases. For each test case: The first line contains two integers $n, k$ ($2 \le n \le 2 \times 10^5, 1 \le k \le 10^9$) representing the number of gates and the duration of the state switch for each gate, respectively. The second line contains $n-1$ integers $t_2, \dots, t_n$ ($1 \le t_i \le 10^9$) representing the travel time between adjacent gates. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output a single line containing a real number representing the mathematical expectation of the total time spent. Your answer is considered correct if the relative or absolute error between your answer and the standard answer does not exceed $10^{-9}$.

Specifically, if your answer is $a_i$ and the standard answer is $b_i$, your answer will be accepted if and only if $\frac{|a_i - b_i|}{\max(1, |b_i|)} \le 10^{-9}$.

Examples

Input 1

2
4 27
9 2 10
6 51
3 3 16 6 10

Output 1

27.750000000
50.750000000