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.
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 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 each pass safely.
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!”.