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 ai (0 ≤ ai ≤ 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.