Cover Up

In the TV game-show game Cover Up, a contestant tries to name the exact retail price of a new car by choosing digits from a board such as:

        9
      3 4
    0 4 7
  9 6 7 3
1 4 8 2 6
3 2 4 0 8

The price has one digit per column, and the contestant picks one number from each column to form a bid. For the board above, the first (leftmost) digit of the price is either 1 or 3; the second is one of 9, 4, 2; the third is one of 0, 6, 8, 4; and so on. A digit can never move to a different column.

After the contestant locks in a bid, the host lights up every digit that is correct. If none are correct, the game ends and the contestant loses. If at least one is correct, the game continues.

When the game continues, the correct digits stay fixed, and for every column that is still wrong the contestant makes a new choice, picking a different, not-yet-tried digit from that same column. Again the host lights up any newly correct digit. If no new digit is correct, the game ends in a loss; if at least one new digit is correct, the game continues. Play repeats until either the contestant loses or every column is correct (a win).

Here is one full round of play:

        9              9              9 
      3 4            3 4            3 4
    0 4 7          0 4            0 4 
  9 6 7 3   ->   9     3    ->  9 
1 4 8 2 6          8 2 6            2 6
3 2 4 0 8      3 2 4 0 8      3 2 4 0 8
| | | | |          |   |          |
v v v v v          v   v          v

               1 4 6 7 7      1 4 8 7 3
               c c x c x      c c x c c

               INITIAL BID    SECOND BID

The contestant starts with the bid $14677. The 1, 4 and first 7 are correct (c marks a correct digit, x an incorrect one, and v marks a column that still needs another pick). The contestant covers the wrong 6 and 7 with an 8 and a 3, making the second bid $14873. The 3 is correct but the 8 is wrong. Now it is a 50/50 chance: the contestant will pick the 4 or the 0 and either win the car or lose the game.

Assume the contestant always picks uniformly at random among the digits that remain in each unfinished column. Compute the probability that the contestant eventually wins the car.

The first line contains an integer $N$ ($N \le 5000$), the number of boards to analyze. The boards follow.

Each board begins with a line containing an integer $d$ ($0 < d \le 7$), the number of digits in the car's price. The next $d$ lines each contain a non-empty string of distinct digits between 0 and 9. Each such line is one column of the board: the first line is the leftmost column and the last line is the rightmost column. A price may legitimately start with the digit 0.

For each board, print on its own line the probability that the contestant wins the car, rounded to exactly 3 decimal places (ties rounded up).