E :: Jenga

Time Limit: 2 Seconds Memory Limit: 65536 KB

In their spare time of training, Alice and Charles often play Jenga together. As they've played the game together so many times, they both know each others' performance as well as themselves'. Now with their success rate of each move provided, can you tell in what probability each of them will win? And of course, Alice and Charles, as well as other ACM-ICPC contestants such as you, are very clever.

Jenga is a game of physical and mental skill. In Jenga, players take turns to remove a block from a tower and balance it on top, creating a taller and increasingly unstable structure as the game progresses.

Jenga is played with 54 wooden blocks. Each block is three times as long as it is wide. To set up the game, the included loading tray is used to stack the initial tower which has 18 levels of three blocks placed adjacent to each other along their long side and perpendicular to the previous level (so, for example, if the blocks in the first level lie lengthwise north-south, the second level blocks will lie east-west).

Once the tower is built, the players take turns to move. Moving in Jenga consists of taking one and only one block from any level (except those mentioned later) of the tower, and placing it on the topmost level in order to complete it. The blocks in the top level, and the level below it if the top level is not completed, cannot be removed. However, if the top level is completed, the blocks in the one below it can be removed. The removed block should be placed to make the top level as same as the other levels (with no block removed). The move is successful if the tower does not fall.

The game ends when the tower falls, or no block can be removed without making the tower fall (rarely happened). And the loser is the player who made the tower fall (i.e., whose turn it was when the tower fell), or who cannot make the move.

Now let's consider each level of the tower, there're only four types of valid arrangement of wooden blocks, as illustrated above. At the beginning of the game, they're all of the type A (or rotated by 90 degrees). And by removing a block from type A, one will get either type B or type C (or the mirrored equivalent of type C). No block from type B can be removed without making the tower fall. From type C we can only remove a block and result in type D. Then no block can be removed further. So there are only three types of moves: (1) A -> B, (2) A -> C and (3) C -> D, while the removed block is added to the top level in addition.

As Alice and Charles have played Jenga so many times, their success rate of each move is very stable and can be formulated as P = b - d*n, where b is the player's base success rate of this type of move, d is the decrease of success rate for each additional level, and n is the number of levels in the tower before this move. The incomplete top level also counts as one level. For example, if the game begins with 18 levels, and both players have the same performance with b = 2.8 and d = 0.1, then P will be 1.0 for the first turn, and become 0.9 between the 2nd and the 4th turns. If P does not lie in the range [0, 1], the nearest number in the range is indicated. (E.g. when a player cannot fail the first several moves, P will be more than 1 until n is a bit larger.)

Input

The input file contains multiple test cases. The first line of the input file is a single integer T (T ≤ 500), the number of test cases.

Each test cases begins with a line of n₀ (3 ≤ n₀ ≤ 18), the number of levels in the tower when the game starts. (When n₀ is not 18, the rules are the same.) The second line contains 6 real numbers b_a1, d_a1, b_a2, d_a2, b_a3, d_a3, indicating Alice's base success rates and the decreases of success rates for each of the three moves: (1) A -> B, (2) A -> C and (3) C -> D. The third line also contains 6 real numbers b_c1, d_c1, b_c2, d_c2, b_c3, d_c3, those of Charles. (0 ≤ b - d*n₀ ≤ 2 and 0 < d ≤ 0.5 for all the 6 pairs of parameters. No real number will have more than 4 digits after the decimal point.)

Output

For each test case, print a line with Alice's winning probability, assume that she always moves first. Your answer should be rounded to the 4th digit after the decimal point.

Sample Input

2
3
1.3 0.1 1.3 0.1 1.3 0.1
1.3 0.1 1.3 0.1 1.3 0.1
4
1.5 0.1 1.5 0.1 1.5 0.1
1.5 0.1 1.5 0.1 1.5 0.1

Sample Output

0.1810
0.8190

Submit