Route

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Sichuan province is saturated with many beautiful, stirring and mysterious stories about the Three Kingdoms. Ancient Jianmen Trail is especially a good resort with both beautiful scenery and culture. The most exciting story, among many others, is Riding Alone for Thousands of Miles, an interesting description about Guan Yu, a senior general, who, upon hearing about the situation of his sworn brother Liu Bei, gave up all the excellent offers by Cao Cao and embarked of the road to look for Liu. Broasword on back, followed by Liu’s family, ridding on his treasured horse, Guan started from Xudu, and finally found Liu in Gucheng after overcoming all the difficulties in his way.

Now, your task is to design a new route for Guan Yu to find his brother. Suppose that Guan Yu knew all the connections between the passes from Xudu to Gucheng, and the probability to defeat the guards on each pass to go through safely. Please help Guan Yu find a successful route from Xudu to Gucheng with a maximum of probability. Guan Yu cannot go to each pass twice.
 

Input

The first line of the input contains an integer T(1 <= T <= 50). T refers to the number of the test cases followed.

For each test case, the first line contains only one integer N (3 <= N <= 1000). The following N lines are a matrix representing the connections among the N-2 passes from Xudu to Gucheng. If the number of the ith row and the jth column is 1, this means that there is a connection from i to j. Otherwise, the number of 0 means no connection from i to j. The last line of each test case contains N-2 real numbers separate by a single blank, and each real number represents the probability P (0 <= P <= 1) of Guan Yu going through the pass safely.
 

Output

For each test case you should output one line containing only real number representing the maximum probability of Guan Yu to arrive in Gucheng safely. The real number is rounded to four decimal digits. If the result is less than 0.0001, then output “Cannot reach!”.

Sample Input

3
3
0 1 0
0 0 1
0 0 0
0.5
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
0.01 0.001
6
0 1 1 0 0 0 
0 0 1 1 0 0
0 0 0 1 1 0
0 0 1 0 1 1
0 0 0 0 0 1
0 0 0 0 0 0
0.2 0.1 0.6 0.3

Sample Output

0.5000
Cannot reach!
0.1200

Hint

 

Source

2008湖南大学校赛