// NWERC'10 solution for problem 'risk'
// Jaap Eldering

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int infty = 99999999;

VVI cap, flow;

int source, sink;
VI parent;

int findpath()
{
	VI used(cap.size(),0);
	queue<int> que;

	que.push(source);
	used[source] = 1;

	while ( !que.empty() && !used[sink] ) {
		int t = que.front(); que.pop();

		for(unsigned i=0; i<cap.size(); i++) {
			if ( !used[i] && cap[t][i]-flow[t][i]>0 ) {
				used[i] = 1;
				parent[i] = t;
				que.push(i);
			}
		}
	}

	return used[sink];
}

int pushflow()
{
	int val = infty;
	int tmp = sink;

	while ( tmp!=source ) {
		val = min(val,cap[parent[tmp]][tmp]-flow[parent[tmp]][tmp]);
		tmp = parent[tmp];
	}

	tmp = sink;
	while ( tmp!=source ) {
		flow[parent[tmp]][tmp] += val;
		flow[tmp][parent[tmp]] -= val;
		tmp = parent[tmp];
	}

	return val;
}

int maxflow()
{
	int res = 0;
	flow = VVI(cap.size(), VI(cap.size(), 0));
	parent = VI(cap.size());

	while ( findpath() ) res += pushflow();
	return res;
}

int main()
{
	int run, nruns;

	cin >> nruns;

	for(run=1; run<=nruns; run++) {
		int N, M, B = 0;
		char c;
		cin >> N;
		VI armies(N,0), border(N,0), mine;
		VVI conn(N,VI(N,0));
		for(int i=0; i<N; i++) cin >> armies[i];
		for(int i=0; i<N; i++) {
			if ( armies[i]>0 ) mine.push_back(i);
			for(int j=0; j<N; j++) {
				cin >> c;
				if ( c=='N' ) continue;
				conn[i][j] = 1;
				if ( armies[i]>0 &&
				     armies[j]==0 && !border[i] ) { border[i] = 1; B++; }
			}
		}
		M = mine.size();

		// Consistency checks:
		if ( B==0 ) return 1;
		for(int i=0; i<N; i++) {
			if ( conn[i][i] ) return 1;
			for(int j=0; j<i; j++)
				if ( conn[i][j]!=conn[j][i] ) return 1;
		}

		cap = VVI(2*M+2,VI(2*M+2,0));
		source = 2*M;
		sink = 2*M+1;

		for(int i=0; i<M; i++) {
			cap[source][i] = armies[mine[i]];
			cap[M+i][sink] = 1;
			for(int j=0; j<M; j++) cap[i][M+j] = infty*conn[mine[i]][mine[j]];
			cap[i][M+i] = infty;
		}

		int lo, mid, hi;
		lo = 0;
		hi = 20000;
		while ( lo+1<hi ) {
			mid = (lo+hi+1)/2;

			for(int i=0; i<M; i++) if ( border[mine[i]] ) cap[M+i][sink] = mid;

			if ( maxflow()==mid*B+(M-B) ) {
				lo = mid;
			} else {
				hi = mid;
			}
		}

		cout << lo << endl;
	}

	return 0;
}
