import java.io.*;
import java.util.*;

public class adrian {
	// augment flow by one unit if possible
	public static boolean augmentFlow(int [][] E, int [][] C, int s, int t) {
		int n = C.length;
		int [] P = new int[n];
		int [] Q = new int[n];
		int len = 1;
		P[s] = -1;
		Q[0] = s;
		for (int i=0; i<len; ++i) {
			int u = Q[i];
			for (int v : E[u]) {
				if (C[u][v] > 0 && P[v] == 0) {
					P[v] = u+1;
					if (v == t) {
						while (P[v] != -1) {
							u = P[v]-1;
							--C[u][v];
							++C[v][u];
							v = u;
						}
						return true;
					}
					Q[len++] = v;
				}
			}
		}
		return false;
	}
	public static int buildGraph(int [] a, String [] borders, int [] len, int [][] C, int [][] E, int [] s) {
		int N = len.length;
		int n = N/2-1;
		int special = 0;
		for (int i=0; i<n; ++i)
			if (a[i] > 0) {
				if (a[i] > 1) {
					if (E != null) {
						E[0][len[0]] = i+n+1;
						E[i+n+1][len[i+n+1]] = 0;
						C[0][i+n+1] = a[i]-1;
					}
					++len[0];
					++len[i+n+1];
				}
				if (E != null) {
					E[i+1][len[i+1]] = i+n+1;
					E[i+n+1][len[i+n+1]] = i+1;
					C[i+n+1][i+1] = a[i];
				}
				++len[i+1];
				++len[i+n+1];
				boolean outer = false;
				for (int j=0; j<n; ++j)
					if (borders[i].charAt(j) == 'Y') {
						if (a[j] == 0)
							outer = true;
						else {
							if (E != null) {
								E[i+1][len[i+1]] = j+n+1;
								E[j+n+1][len[j+n+1]] = i+1;
								C[i+1][j+n+1] = a[i];
							}
							++len[i+1];
							++len[j+n+1];
						}
					}
				if (outer) {
					if (E != null) {
						s[special] = i;
						E[i+n+1][len[i+n+1]] = N-1;
						E[N-1][len[N-1]] = i+n+1;
					}
					++special;
					++len[i+n+1];
					++len[N-1];
				}
			}
		return special;
	}
	public static void main(String [] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		while(tc-- > 0) {
			int n = Integer.parseInt(in.readLine());
			int [] a = new int[n];
			StringTokenizer strtok = new StringTokenizer(in.readLine());
			for (int i=0; i<n; ++i)
				a[i] = Integer.parseInt(strtok.nextToken());
			String [] borders = new String[n];
			for (int i=0; i<n; ++i)
				borders[i] = in.readLine();
			int N = n*2 + 2;
			int [][] C = new int[N][N];
			int [][] E = new int[N][1];
			int [] len = new int[N];
			// first count number of adjacent edges for each node
			int special = buildGraph(a, borders, len, null, null, null);
			int [] s = new int[special];
			for (int i=0; i<N; ++i) {
				E[i] = new int[len[i]];
				len[i] = 0;
			}
			// now really build the graph
			buildGraph(a, borders, len, C, E, s);
			int res = 0;
			boolean stop = false;
			while(!stop) {
				++res;
				for (int i=0; i<special; ++i)
					++C[s[i]+n+1][N-1];
				for (int i=0; i<special; ++i)
					if (!augmentFlow(E, C, 0, N-1)) {
						stop = true;
						break;
					}
			}
			System.out.println(res);
		}
	}
}
