/* NWERC 2010: Sample solution to "Risk"
 * Author: Sean Lip
 *
 * Algorithm: maximum flow with binary search
 */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;

int NN;
int caps[410][410];
int flow[410][410];

int p[410];
long long f[410];
bool seen[410];

int ans;

int maxFlow(int source, int sink)
{
	memset(flow,0,sizeof flow);
	ans = 0;
	while(1)
	{
		memset(p,-1,sizeof p);
		memset(f,0,sizeof f);
		memset(seen,0,sizeof seen);
		
		f[source] = 9999999;

		deque<int> Q;
		Q.push_back(source);
		seen[source] = 1;
		p[source] = source;
		
		while(Q.empty() == 0)
		{
			long long k = Q[0];
			Q.pop_front();

			for(int t = 0; t < NN; t++)
				if(seen[t] == 0 && (caps[k][t] > flow[k][t] || flow[t][k] > 0))
				{
					if(caps[k][t] > flow[k][t])
						f[t] = min((long long)caps[k][t]-flow[k][t], f[k]);
					else
						f[t] = min((long long)flow[t][k], f[k]);
					
					p[t] = k;					
					seen[t] = 1;
					Q.push_back(t);
				}
		}
		
		if(f[sink] == 0) break;
		
		ans += f[sink];
		
		int curr = sink;
		while(curr != source)
		{
			int prev = p[curr];
			if(caps[prev][curr] - flow[prev][curr] >= f[sink])
				flow[prev][curr] += f[sink];
			else flow[curr][prev] -= f[sink];
			
			curr = prev;
		}
		
	}
	return ans;
}

int main()
{
	int T;
	scanf("%d",&T);
	
	for(int t = 0; t < T; t++)
	{
		int N;
		scanf("%d",&N);
		
		int armies[200];
		for(int i = 0; i < N; i++)
			scanf("%d",&armies[i]);
		
		char c;
		bool G[200][200];
		for(int i = 0; i < N; i++)
		{
			scanf("%c",&c);
			for(int j = 0; j < N; j++)
			{
				scanf("%c",&c);
				if(c == 'Y') G[i][j] = 1;
				else G[i][j] = 0;
			}
		}
		
		int myside = 0;
		int numSinks = 0;
		bool isasink[200];
		memset(isasink,0,sizeof isasink);
		int sinks[200];
		for(int i = 0; i < N; i++)
		if(armies[i] != 0)
		{
			myside++;
			for(int j = 0; j < N; j++)
			if(G[i][j] && armies[j] == 0)
			{
				isasink[i] = 1;
				sinks[numSinks++] = i;
				break;
			}
		}
	
		for(int i = 0; i < N; i++)
			G[i][i] = 1;
			
		//0 to N-1 are orig nodes. N to 2N-1 are sink nodes.
		//Source is 2N, sink is 2N+1.
		
		int source = N + N, sink = N + N + 1;
		NN = sink + 1;
		
		memset(caps,0,sizeof caps);
		memset(flow,0,sizeof flow);
		
		for(int i = 0; i < N; i++)
			caps[source][i] = armies[i];
		
		for(int i = 0; i < N; i++)
		if(armies[i] != 0)
		{
			for(int j = 0; j < N; j++)
				if(G[i][j] && armies[j] != 0)
					caps[i][N + j] = 100;
		}
		
		int maxAns = 0;
		ans = 0;
		
		int target = myside;

		int offset = 0;
		int minCap = 1;
		int maxCap = 20001;
		
		while(maxCap > minCap)
		{
			int midCap = (minCap + maxCap + offset%2)/2;
			offset++;

			for(int i = 0; i < N; i++)
				if(armies[i] != 0)
					caps[N+i][sink] = 1;
				else caps[N+i][sink] = 0;
		
			for(int i = 0; i < numSinks; i++)
				caps[N+sinks[i]][sink] += midCap-1;

			target = myside + numSinks*(midCap-1);
			
			if(maxFlow(source,sink) >= target)
				minCap = midCap;
			else maxCap = midCap-1;
		}
		printf("%d\n",maxCap);
	}
	return 0;
}

