Tournament

A martial arts tournament is held in a certain city. $N$ competitors take part, two of whom are brothers: Olek and Felek.

Every match is fought between two competitors and has exactly one winner, who stays in the tournament, while the loser is eliminated. The order of matches is fixed before the tournament by a "tournament tree". The picture below shows an example tournament tree for four competitors: competitors "start" in the yellow fields, and the green fields are matches.

At the start of the tournament the competitors are drawn to the starting positions uniformly at random, so every assignment of competitors to the yellow fields is equally likely.

This year the field is so even that you should assume every match is won with equal probability ($\frac{1}{2}$) by each of its two competitors.

Compute the probability that at some point during the tournament the brothers Olek and Felek fight each other.

The first line contains the number of test sets $Z$ ($1 \le Z \le 5$). The descriptions of the sets follow.

Each set begins with a line containing an integer $N$ ($2 \le N \le 1000$), the number of competitors. The next $N - 1$ lines describe the tournament matches, numbered from $1$ to $N - 1$, one match per line.

Each match description is two strings separated by a single space; each string names one of the two competitors in that match:

• Z<k> (for example Z1, Z4, with $1 \le k \le N$) is the competitor placed at starting position $k$.
• P<k> (for example P1, P4, with $1 \le k \le N - 1$) is the winner of match number $k$.

The input always describes a valid tournament tree: every starting position feeds exactly one match, and the winner of every match except one (the final) feeds exactly one later match.

For each set, print on its own line the probability that Olek and Felek fight each other, rounded to exactly four digits after the decimal point, rounding half up (for example, 0.5000).