Risk is a board game played on a world map. This world is
divided into regions by borders. Each region is controlled by a
player (either you or one of your opponents). Any region that
you control contains a positive number of your armies.
In each turn, you are allowed to move your armies. Each of
your armies may either stay where it is, or move from a region
to a bordering region under your control. The movements are
performed one by one, in an order of your choice. At all times,
each region must contain at least one army.
For strategic purposes, it is important to move your armies
to regions that border your opponents’ regions and minimize the
number of armies on your regions that are totally surrounded by
other regions under your control. You want your weakest link,
i.e., the border region with the minimum number of armies, to
be as strong as possible. What is the maximum number of armies
that can be placed on it after one turn?
Input
On the first line a positive integer: the number of test
cases, at most 100. After that per test case:

One line with an integer $n$ ($1\le n\le 100$): the number of
regions.

One line with $n$
integers $a_ i$
$(0\le a_ i\le 100)$:
the number of your armies on each region. A number
$0$ indicates that a
region is controlled by your opponents, while a positive
number indicates that it is under your control.

$n$ lines with
$n$ characters, where
each character is either ‘Y’ or
‘N’. The $i$th character of the
$j$th line is
‘Y’ if regions $i$ and $j$ border, and ‘N’ otherwise. This relationship is
symmetric and the $i$th character of the
$i$th line will
always be ‘N’.
In every test case, you control at least one region, and
your opponents control at least one region. Furthermore, at
least one of your regions borders at least one of your
opponents’ regions.
Output
Per test case:
Sample Input 1 
Sample Output 1 
2
3
1 1 0
NYN
YNY
NYN
7
7 3 3 2 0 0 5
NYNNNNN
YNYYNNN
NYNYYNN
NYYNYNN
NNYYNNN
NNNNNNY
NNNNNYN

1
4
