/*
	[NWERC'10] RISK
	by: Jan Kuipers
*/

#include <iostream>
#include <vector>

using namespace std;

int M;
vector<int> u;
vector<vector<int> > cap;

int go (int n) {

	if (n==0) u=vector<int>(M,0);
	if (n==1) return 1;

	u[n]=1;
	
	for (int i=0; i<M; i++)
		if (!u[i] && cap[n][i]>0 && go(i)) {
			cap[n][i]--;
			cap[i][n]++;
			return 1;
		}

	return 0;
}

int main () {

	int runs;
	cin>>runs;

	while (runs--) {

		int N;
		cin>>N;

		int A=0;
		vector<int> a(N);
		for (int i=0; i<N; i++) {
			cin>>a[i];
			if (a[i]>0) A++;
		}

		vector<string> c(N);
		for (int i=0; i<N; i++)
			cin>>c[i];

		vector<int> b(N,0);
		for (int i=0; i<N; i++)
			for (int j=0; j<N; j++)
				if (c[i][j]=='Y' && a[i]>0 && a[j]==0)
					b[i]=1;

		M = 2*N+2;
		
		cap = vector<vector<int> >(M, vector<int>(M, 0));
		
		for (int i=0; i<N; i++)
			for (int j=0; j<N; j++)
				if (c[i][j]=='Y' || i==j)
					cap[i+2][N+j+2]=999;

		for (int i=0; i<N; i++)
			cap[0][i+2]=a[i];

		int need=0;
		for (int i=0; i<N; i++) 
			if (a[i]>0) {
				cap[N+i+2][1]++;
				need++;
			}

		int res=0;
		
		while (1) {
			
			while (need>0 && go(0)) need--;
			
			if (need>0) break;
			res++;
			
			for (int i=0; i<N; i++) 
				if (b[i]) {
					cap[N+i+2][1]++;
					need++;
				}
		}

		cout << res << endl;
	}
	
	return 0;
}
