Consensus

One of the most fundamental problems in the field of distributed
computing is consensus.  In the problem, there are some processes that
are connected by a network and can communicate using messages. Each of
them has some initial preferred value.  In order to solve consensus,
those processes have to finally agree upon some value, i.e. each one
of them has to output the same value.  That common output value should
be the original preferred value of some process.  (Otherwise the
problem could be trivially solved by having all processes always
output 0.)  Here, we will focus on a synchronous system, i.e. a system
in which all processes run at the same speed, acting in rounds and the
messages sent at the beginning of a round reach receivers during that
round.

Let's assume we will run the following algorithm to solve consensus: 
 - In each round every process will send his current preference value
to all of its neighbours in the network.
 - If, at the end of the round, some preference value received by it
is smaller that his own preference value, he will switch his
preference to the smallest value received in this round.

Your task is to determine how long it takes for the algorithm to reach
a consensus, i.e. how many rounds have to pass until all processes
have the same preference.

For example, suppose there are three processes A, B, C.  A can send
messages to B and C, B can send messages to A and C can send messages
to B.  (The network connections don't have to be symmetric, i.e. it's
possible that process X can send messages to process Y, but Y can't
send messages to X).  Suppose A's initial preference is 4, B's initial
preference is 3 and C's initial preference is 2.  At the beginning,
the preference values of the processes differ, so consensus has not
yet been reached.  
In the first round:
	A will send 4 to B and C, 
	B will send 3 to A
	C will send 2 to B
At the end of the round, C will not change its preference value, but 
A will switch to 3 and B will switch to 2.
In round #2:
	A will send 3 to B and C,
	B will send 2 to A,
	C will send 2 to B
At the end of round 2, all processes will have preference 2, and
consensus will be reached.

Input

Input will consist of multiple test cases. In the first line of input,
there will be a single positive integer T equal to the number of test
cases.  Then, there will be T test cases, each in the following format:
In the first line, there will be a single positive integer n, where n
is the number of processes in the network (n < 101).  Then, n lines
will follow, each containing a string of n 'r' or 'u' characters.  If
the j-th character in the i-th line is an 'r' then process i can send
a message directly to process j.  If the j-th character in the i-th
line is 'u', then process i cannot send a direct message to j.
In the last line of each test case, there will be n positive integer
values, separated by single spaces.  The i-th value corresponds to the
initial preference value of the i-th process.  The values will not be
greater than one thousand.

Output

For each test case your program should output a single line with the
number of rounds that it takes for all the processes to reach consensus. 

If the consensus will never be reached, output -1.

The rounds are numbered starting from 1. Hence, if the the system is
initially in the state of consensus, you should output 0, whereas, if
consensus is reached at the end of the first round, you should output
1.

Sample Input

4
4
urrr
rurr
rrur
rrru
1 2 7 9
3
uru
ruu
uru
4 1 5
2
uu
uu
7 7
5
uruuu
uuruu
uuuru
uuuur
ruuuu
171 160 152 121 99

Sample output

1 
-1 
0 
4