Hamlet

Imagine you come home from your first year at university and find that your father has died and that your uncle, your father's brother, has married your mother. Soon after, your father's ghost appears and tells you that the uncle murdered him. On top of that, you are the prince of Denmark and the uncle is the new king. That is how the play Hamlet begins. Hamlet is upset, and he thinks the situation through in his famous soliloquy:

To be, or not to be: that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles
And by opposing end them. [...]

Hamlet weighs the courses of action open to him, suicide among them. Every outcome is uncertain. He might sleep deeply, a good outcome, or be tormented by dreams in death, a bad one. Later, while he talks to his mother, he hears a noise behind a curtain and stabs through it without knowing who is there. Had it been the uncle, the story could have ended well. It was the father of the woman he loves, and she then drowns, a bad outcome. Hamlet has to take many actions whose outcomes are uncertain. Help him choose, so that the story does not end with the whole House of Denmark dead.

You are given the states the plot can be in, such as "beginning", "Hamlet has killed himself and sleeps peacefully", "Hamlet has killed himself and is tormented in hell", "Hamlet has stabbed his uncle Claudius", or "Hamlet has stabbed Polonius and Ophelia has drowned". A state can be the end of the story, and then the state has a value. Otherwise Hamlet has one or more actions available, and each action gives a probability distribution over the states that can follow it. If he stabs the person behind the curtain, it may be Claudius with probability 0.4, Polonius with probability 0.5, and a servant with probability 0.1, which leads to three different plot states.

The plot never runs in a cycle. The states are numbered 1 to $n$, and every action gives probability 0 to moving from a state to a state with a lower or equal number. The story starts in state 1.

Here is how the arithmetic works. Suppose Hamlet can choose whether or not to stab the curtain. Claudius behind the curtain ends the plot with value 3. A servant ends it with value -1. Polonius behind the curtain makes Ophelia drown and makes Laertes challenge Hamlet to a fencing match with a secretly poisoned sword. If Hamlet accepts, both die and the value is -10. If he rejects, both still die from poisoned wine with probability 0.5, and otherwise both live while Polonius and Ophelia stay dead, for value -5. Rejecting is worth $0.5 \times (-10) + 0.5 \times (-5) = -7.5$, so stabbing the curtain is worth $0.4 \times 3 + 0.1 \times (-1) + 0.5 \times (-7.5) = -2.65$. That number is then compared with the value of not stabbing the curtain, which is computed the same way.

Print the largest expected value Hamlet can reach from state 1 when he picks a best action in every state he arrives in.

The first line contains an integer $K$ ($K \ge 1$), the number of data sets in the input. $K$ data sets follow.

The first line of a data set contains an integer $n$ ($1 \le n \le 1000$), the number of plot states.

Then come the descriptions of the $n$ states, for $i = 1$ up to $n$ in order. The first line of the description of state $i$ is an integer $a_i$ ($0 \le a_i \le 5$), the number of actions Hamlet can choose from in state $i$.

If $a_i = 0$, the next line contains one real number $v_i \in [-1000, 1000]$, the value of the ending $i$.

If $a_i > 0$, then $a_i$ lines follow. Line $k$ contains $n$ real numbers $p^{(k)}_{i,1}, \ldots, p^{(k)}_{i,n}$ with $p^{(k)}_{i,j} \in [0, 1]$ and $\sum_j p^{(k)}_{i,j} = 1$. They are the probabilities of moving from state $i$ to state $j$ when Hamlet takes action $k$ in state $i$. Every $p^{(k)}_{i,j}$ with $i \ge j$ is 0, so state $n$ is always an ending and $a_n = 0$.

The answer of a data set differs by at least $10^{-6}$ from every midpoint between two neighboring two decimal numbers, so the rounding described below is never ambiguous.

For each data set, print Data Set x: on a line of its own, where $x$ is the number of the data set, counted from 1. On the next line print the maximum expected value Hamlet can guarantee himself, rounded to two decimal places. Print one blank line after each data set. If the rounded value is zero, print 0.00 and never -0.00.