hackercupai/hackercup huggingface dataset:
Mr. Fox has opened up a fabulous Fock farm! A Fock is a cute little animal
which can have either red, green, or blue fur (these 3 possible colors can be
numbered 1, 2, and 3, respectively). Furthermore, a Fock's fur color can
change every second!

Mr. Fox owns a flock of **N** Focks, with the **i**th one initially having a
color of **Ci**. Every second, if the **i**th Fock currently has a color of
**a**, it will switch to having a color of **b** for the next second with
probability **Pi,a,b**%. All Focks change color simultaneously.

After a very large amount of time has gone by, Mr. Fox will take a single
photo of all of his Focks to help advertise his farm. In particular, he picks
an integer **t** at uniform random from the range [10100, 101000] and waits
that many seconds. He's hoping that the photo will make it look like his farm
has a well-balanced mix of Fock colors — it'll be no good if the photo ends up
featuring a strict majority of a single color (that is, strictly more than
**N**/2 of the Focks having the same color). What's the probability of this
occurring?

### Constraints

1 ≤ **T** ≤ 20
1 ≤ **N** ≤ 50,000
1 ≤ **Ci** ≤ 3 for all **i**
0 ≤ **Pi,a,b** ≤ 100 for all **i**, **a** and **b**
**Pi,a,1** \+ **Pi,a,2** \+ **Pi,a,3** = 100 for all **i** and **a**

### Input

Input begins with an integer **T**, the number of Fock farms Mr. Fox has. For
each farm, there is first a line containing the integer **N**. Then, for each
Fock **i**, 4 lines follow. The first of these lines contains the integer
**Ci**. The next three lines contain three space-separated integers each, with
the **b**th integer on the **a**th line being **Pi,a,b**.

### Output

For the **i**th farm, print a line containing "Case #**i**: " followed by the
probability that the **i**th picture contains a strict majority of some color
of Fock, rounded to 6 decimal places.

Absolute errors of up to 2e-6 will be ignored.

### Explanation of Sample

In the first case, the first Fock never changes color, so it'll still have
color 1 in the photo. The second Fock is likely to have color 2 for a while,
but by the time the photo is taken, it'll certainly have color 3. The third
Fock will have either color 2 or 3 in the photo, with equal probability.
Therefore, the photo will have a 50% chance of having a strict majority of
color 3, and a 50% chance of no strict majority.