Migrated from Lutece 108 DaFuWeng

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

After this contest, lxhgww and hhb will formally say farewell to ACM/ICPC, which means the drop scene for the time of ACMilan!!! To recall the happy memory in the summer of 2007, after a busy training day, the three guys prefer to play a game, the DaFuWeng!

The game is played on a line of grids, the player have an unusual dice which gets numbers from $0$ to $N$. In each round of game, player can throw out the dice and get a number Num, then he will step forward Num steps. If you get out of the grids, you have to throw the dice again. There are some fruits lie in the grid, for each grid you get in at first, you can take the fruits.

When you throw out the dice, assume the probability for each number you get is the same, so ACMilan want to know the mathematical expectation of fruits you can get.

Input

The first line of the input contains one integer $T$, which indicates the number of test cases. For each test case, in the first line, there are two integers $M$ and $N$, where $M$ is the number of grids in this game and $N$ is the number describing dice as aforementioned. ($M\leq 10^5$, $1\leq N\leq 6$). Following $M$ lines have one integer in each. The integer in $i_{th}$ line is the number of fruits in the $i_{th}$ grid. Note that, in the beginning of the game, you are supposed to stand in the $0_{th}$ grid. When you step in to the $M_{th}$ grid, the game is over.

Output

For each case, output one line containing the expectation of fruits you can get. And remember to round the answer to the first digit after the decimal point.

Samples

1
2 1
5
6

11.0

Resources

The 7th UESTC Programming Contest Final