#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define INF 10000000
#define MAXN 200
#define MAXNODES (MAXN*2+2)
#define QUEUE_LEN (MAXNODES*MAXNODES)
#define MIN(x, y) ((x) < (y) ? (x) : (y))

int cap[MAXNODES][MAXNODES];
int flow[MAXNODES][MAXNODES];
int neighbours[MAXNODES][MAXNODES];
int neighbours_count[MAXNODES];
bool neighbours_added[MAXNODES][MAXNODES];
int parent[MAXNODES];
int path_capacity[MAXNODES];
int queue[QUEUE_LEN];

void initflow() {
	memset(cap, 0, sizeof(cap));
	memset(neighbours_count, 0, sizeof(neighbours_count));
	memset(neighbours_added, false, sizeof(neighbours_added));
    memset(flow, 0, sizeof(flow));
}

void addflow(int f, int t, int c) {
	cap[f][t] += c;
	if(!neighbours_added[f][t]) {
		neighbours[f][neighbours_count[f]++] = t;
		neighbours[t][neighbours_count[t]++] = f;
		neighbours_added[f][t] = neighbours_added[t][f] = true;
	}
}

int maxflow(int n, int s, int t)
{
    int flow_size, qbottom, qlen, u, v, i;

    flow_size = 0;

    while (1) {
        for (v = 0; v < n; v++)
            parent[v] = -1;

        parent[s] = -2;
        path_capacity[s] = INF;

        qbottom = 0;
        queue[0] = s;
        qlen = 1;

        while (qlen > 0 && parent[t] == -1) {
            u = queue[qbottom++];
            qlen--;
            for (i = 0; i < neighbours_count[u]; i++) {
                v = neighbours[u][i];
                if (cap[u][v] > flow[u][v] && parent[v] == -1) {
                    parent[v] = u;
                    path_capacity[v] = MIN(path_capacity[u], cap[u][v] - flow[u][v]);
                    if (v != t)
                        queue[qbottom + qlen++] = v;
                    else
                        break;
                }
            }
        }

        if (parent[t] == -1)
            return flow_size;

        flow_size += path_capacity[t];

        v = t;
        while (v != s) {
            u = parent[v];
            flow[u][v] += path_capacity[t];
            flow[v][u] -= path_capacity[t];
            v = u;
        }
    }
}

int a[MAXN];
bool conn[MAXN][MAXN];

void testcase() {
	int i, j, ret, n, numborder, nummine;
	bool border;
	scanf("%d\n",&n);
	for(i = 0; i < n; i++)
		scanf("%d",&a[i]);
	scanf("\n");
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++)
			conn[i][j] = (getchar() == 'Y');
		scanf("\n");
	}
	initflow();
	numborder = 0;
	nummine = 0;
	for(i = 0; i < n; i++) {
		if(a[i] > 0) {
			addflow(n+n,i,a[i]);
			addflow(i,i+n,a[i]);
			border = false;
			for(j = 0; j < n; j++) {
				if(conn[i][j] && a[j] == 0)
					border = true;
				if(conn[i][j] && a[i] > 0 && a[j] > 0)
					addflow(i,j+n,a[i]);
			}
			addflow(i+n,n+n+1,1);
			if(border) numborder++;
			nummine++;
		}
	}
	if(maxflow(n+n+2,n+n,n+n+1) != nummine) {
		printf("ERROR\n");
		return;
	}
	ret = 0;
	do {
		for(i = 0; i < n; i++) {
			if(a[i] > 0) {
				border = false;
				for(j = 0; j < n; j++) {
					if(conn[i][j] && a[j] == 0)
						border = true;
				}
				if(border) {
					addflow(i+n,n+n+1,1);
				}
			}
		}
		ret++;
	} while(maxflow(n+n+2,n+n,n+n+1) == numborder);
	printf("%d\n",ret);
}

int main() {
	int t;
	scanf("%d\n",&t);
	while(t--) testcase();
	return 0;
}
