Giải bài trực tuyến

Black-White-Nim is played as follows. There are one or more horizontal rows, each containing several black and white beads. Two players take turns removing beads until there are none left. During each turn, a player must remove one or more consecutive beads from the left end of a single row. The removed beads must contain either no black beads or exactly one black bead. If one black bead is removed, that bead must be the rightmost of the removed beads. The player who takes the last turn wins.

Given the number of black and white beads in each rows. The order of beads in each row is randomly generated at the beginning of the game. Each distinct row ordering is equally likely. Black beads are indistinguishable from one another, and white beads are indistinguishable from one another. Output the probability that the first player will win the game assuming that both players follow an optimal strategy.

Input

The first line of input contains a number representing the number of tests.

Each test cases contains three lines, the first line contains N representing the number of rows.

The second line contains N numbers, representing the number of black beads in each row. There will be at most 100 black beads in each row.

The third line contains N numbers, representing the number of white beads in each row. There will be at most 100 white beads in each row. There will be at least one beads in each row.

Output

For each test case, output a line contains a float-number, representing the answer. It must be printed with exactly six decimal places.

Example

Input:
4
1
0
2
1
2
0
1
2
2
2
2 5
2 0

Output:
1.000000
0.000000
0.666667
0.666667

Constraints

Dataset 1: N ≤ 50. Time limit: 5s