You are in a maze; in front of you there are n doors . You can choose to go through any door you like. The probability for choosing a door is equal for all doors.

If you choose the i^th door, it can either take you back to the same position where you began in x_i minutes, or can take you out of the maze after x_i minutes. If you come back to the same position, you can remember the last K doors you have chosen. And when you are about to choose a door, you never choose a door that is already visited by you. Or we can say that you never choose a door that is visited as one of the last K doors. And the probability of choosing any remaining doors is equal.

Now you want to find the expected time to get out of the maze.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and two integers n K (1 ≤ n ≤ 100, 0 ≤ K ≤ n). The next line contains n space separated integers. If the i^th integer (x_i) is positive, you can assume that the i^th door will take you out of maze after x_i minutes. If it's negative, then the i^th door will take you back to the beginning position after abs(x_i) minutes. You can safely assume that 1 ≤ abs(x_i) ≤ 10000.

For each case, print the case number and the expected time to get out of the maze. If it's impossible to get out of the maze, print -1. Otherwise, print the result. Error less than 10^-6 will be ignored.