SP13592 PRLOVE - Expected Time to Love

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], skipTags: ["script","noscript","style","textarea","code"] } }); 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.

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 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}$.