The FIFA 2010 Soccer World Cup has gone, Small Jan returned to her own planet. After she saw the Spain emerged the biggest winner, she believe that, as a Queen, she can also arrange a captivating match-International Cavalry PK Contest(ACM-ICPC) for her lovely and hard working subjects. But her subjects are so busying that they have no time to watch the group match. So, our smart Queen wants to make the final more valuable. Every Knight has a value in people’s minds and the final’s value is dependent on the last valiancy Knights (equals to the winner's value).
Now assuming that the Knights have been numbered from 1 to N, and any time Small Jan could arrange a match between any two Knights adjacent to each other, but the loser will quit. For example, (1, 2, 3, 4, 5),if the Queen arranged Knights 3 and 4 for a match and Knight 3 lost, then Knights 2 and 4 would be adjacent to each other (the result of each Knight competing with others is saved in a table).
Here, Small Jan want to know the max value of the final, can you help her?
The first line of the input is a single positive integer T(0 < T <= 30), telling the number of test scenarios to follow.
Each scenario begins with a line containing an integer N, 0 < N <= 100, being the number of Knights.
The following line contains N integers, 0 < Vi < 1000, being the value of each Knight in people’s minds.
Thelast is a N × N matrix. If a[i,j] = 1 indicate when Knight i competing with j, Knight i always win, which also means a[j, i] must equals 0 and if i=j, a[i,j] must equals 0.
For each input case, output a line containing a single number, which is the max value of the final, following the case number (start with 1)