Plinko

Plinko is a game played on a nearly vertical board populated with offset rows of pegs. The player chooses one of five slots at the top of the board, drops the chip into it, and watches as the chip bounces down the board. Each time the chip encounters a peg, it bounces either left or right. On a fair Plinko board, the chance is an even 50 percent each way (except on the board edges, where only one choice exists). The chip eventually ends up on the bottom row, and the ending column determines the prize.

As a player in a dishonest Plinko tournament, you know that all of the boards are rigged. The chance for the chip to go right or left at each peg is not always fair. Luckily, you have found a set of schematics that show the percentage chance that a chip will go right at each peg on each board. Now you just need a program to calculate the odds that a particular drop point leads to the chip landing in specified columns.

Here is an example of how a fair Plinko game's probabilities would look:

	a chip starts in one of five lettered
	columns at the top:
	                           prob. chip will go right
	# A # B # C # D # E #            at each peg:
	#                   #       
	# *   *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#                   #
	#   *   *   *   *   #  =======> 1/2 1/2 1/2 1/2
	#                   #
	# *   *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#                   #
	# A * B * C * D * E #  =======> 1/2 1/2 1/2 1/2
	#####################

	a chip ends at the bottom

Here is one possible path for a chip dropped in the A column:

	# | # B # C # D # E #      prob. chip will go right:
	#  \                #
	# * \ *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#   /               #
	#  /*   *   *   *   #  =======> 1/2 1/2 1/2 1/2
	#  \                #
	# * \ *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#    \              #
	# A * | * C * D * E #  =======> 1/2 1/2 1/2 1/2
	#####################

What are the odds that this exact path would be taken? The probability that it first went right was 1/1, the second move (left) was 1/2, the third move (right) was 1/1, and the last move (right) was 1/2. This means the probability of this path being taken was:

1/1 * 1/2 * 1/1 * 1/2 = 1/4 = 25%

However, there are other paths the chip could have taken to arrive on the bottom row in column B, and they must also be considered when determining the probability that the chip ends up in that particular spot.

Notice that the pegs directly below the 'A' and 'E' marks have special values. Since these columns are on the edge of the board, there is only one way for the chip to go. Even the rigged boards follow that rule.

The first line of input contains a single integer $n$, the number of Plinko boards to analyze. The boards follow. Each board is described by four lines that give, as a fraction, the probability that each peg in that row sends a chip landing on it to the right (the numerator and denominator of every fraction are single digits). Rows with five pegs and rows with four pegs alternate, as shown in the figure. Each board is then followed by three lines, each containing the starting and ending column letters for one of the three chips dropped.

For each board, first print a header data set #X, where X is 1 for the first board, 2 for the second, and so on. Then, for each starting/ending column pair, print Y->Z P paths, H% chance, where Y and Z are the starting and ending columns from the input, P is the number of distinct paths connecting them, and H is the percentage chance that a chip dropped into the starting column ends up in the ending column on the bottom row. Truncate (discard) any fractional part of the percentage before printing.