Description

有n个阵地，已知我方在每个阵地上的士兵数，若我方士兵不为0则表示该阵地由我方占领，否则为对方占领。某些阵地之间有通道，我们认为士兵可以经过1单位时间从1个阵地移动到相邻（有通道相连）的阵地。对于一个阵地，如果其相邻的阵地中有非我方阵地，则表示其受到威胁，该阵地中我方人数。

现在求：对我方士兵进行一次1个单位的移动（调动），在保证我方不丢失阵地的情况下（即我方每个阵地上的人数不为0），使得我方所有受到威胁的阵地中人数最少的阵地的人数尽可能多。

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 ≤ n ≤ 100): the number of regions.
• One line with n integers a_i (0 ≤ a_i ≤ 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

Sample Input

Sample Output

Hint

Source