Risk

Risk is a famous board game played on a map of the world. The world is divided by borders into several territories, and each territory belongs to exactly one player. Every territory you own must always be garrisoned by at least one of your armies.

On your turn, you may leave each army where it is or move it one step into an adjacent territory that you own. A single army may move only once, from the territory it occupies at the start of your turn to an adjacent territory; it cannot travel two or more steps in a row. You may, however, perform such moves for as many armies as you like, and you may split the armies of one territory among several destinations. You may never move every army out of a territory, leaving it with a garrison of 0. If you have no army to move, you may simply pass.

A common strategy is to mass as many armies as possible in the territories that touch enemy territory. This turn you want to make your weakest territory, the enemy-adjacent territory holding the fewest armies, as strong as possible. When your turn ends, what is the largest number of armies that can be garrisoned in your weakest territory?

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case is given as follows.

• The first line contains the total number of territories $n$ ($1 \le n \le 100$).
• The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100$), where $a_i$ is the number of your armies garrisoned in territory $i$. If $a_i$ is $0$, that territory is held by the enemy.
• Then $n$ lines follow, each consisting of $n$ characters 'Y' or 'N'. The $j$-th character of the $i$-th line is 'Y' if territories $i$ and $j$ are adjacent and 'N' otherwise. The adjacency is always symmetric, and the $i$-th character of the $i$-th line is 'N' for every $i$.

In every test case you own at least one territory, the enemy owns at least one territory, and at least one of your territories is adjacent to an enemy territory.

For each test case, print on its own line the largest number of armies that can be garrisoned in the weakest territory (the enemy-adjacent territory of yours that holds the fewest armies).