Alice has a problem. She loves Bob but is unable to face up to him. So she decides to send a letter to Bob expressing her feelings. She wants to send it from her computer to Bob's computer through the internet.

The internet consists of $N$ computers, numbered from $1$ to $N$. Alice's computer has the number $1$ and Bob's computer has the number $N$.

Due to some faulty coding, the computers start behaving in unexpected ways. On recieving the file, computer $i$ will forward it to computer $j$ with probability $P_{ij}$. The time taken to transfer the file from computer $i$ to computer $j$ is $T_{ij}$.

Find the expected time before Bob finds out about Alice's undying love for him.

Note: Once the letter is recieved by Bob's computer, his computer will just deliver it to Bob and stop forwarding it.

Input

First line contains $T$, the total test cases.

Each test case looks as follows:

First line contains $N$, the total number of computers in the network.

The next $N$ lines contain $N$ numbers each. The $j$'th number on the $i$'th line is the value $P_{ij}$ in percents.

The next $N$ lines contain $N$ numbers each. The $j$'th number on the $i$'th line is the value $T_{ij}$.

Output

Output a single line with a real number - The expected time of the transfer.

Your output will be considered correct if each number has an absolute or relative error less than $10^{-6}$.

Constraints

$N \le 100$

$T \le 5$

For all $i$, $P_{i1} + P_{i2} + \ldots + P_{iN} = 100$

$P_{NN} = 100$

For all $i$, $j$, $0 \le T_{ij} \le 10000$

You can safely assume that from every computer, the probability of eventually reaching Bob's computer is greater than $0$.

Example

Sample Input:
2
4
0 50 50 0
0 0 0 100
0 0 0 100
0 0 0 100
0 2 10 0
0 0 0 0
0 0 0 0
0 0 0 0
2
99 1
0 100
10 2
0 0

Sample Output:
6.000000
992.000000