// Arup Guha
// 8/31/2013
// Solution to UCF JV Practice Problem F: Parallel Programming

import java.util.*;

public class f {

	public static int n;
	public static int[] times;
	public static int[] curDegrees;
	public static char[][] dependencies;

	public static void main(String[] args) throws Exception {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Get cases.
		for (int loop=0; loop<numCases; loop++) {

			// Read in graph.
			n = stdin.nextInt();
			times = new int[n];
			for (int i=0; i<n; i++)
				times[i] = stdin.nextInt();

			dependencies = new char[n][];
			for (int i=0; i<n; i++)
				dependencies[i] = stdin.next().toCharArray();

			// Count each dependency.
			curDegrees = new int[n];
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					if (dependencies[i][j] == 'Y')
						curDegrees[j]++;

			// Output result.
			System.out.println(process());
		}

		stdin.close();
	}

	public static int process() {

		// Set up valid edges from which to build.
		PriorityQueue<pair> tasks = new PriorityQueue<pair>();
		boolean[] used = new boolean[n];
		int numDone = 0;

		// Put all tasks with no dependencies in the queue.
		int curTime = 0;
		for (int i=0; i<curDegrees.length; i++) {
			if (curDegrees[i] == 0) {
				used[i] = true;
				tasks.offer(new pair(i,curTime+times[i]));
			}
		}

		// Iteratively tasks, as soon as we can do them.
		while (numDone < n) {

			// If we get here with an empty queue, we can't do it!
			if (tasks.size() == 0) return -1;

			pair next = tasks.poll();
			curTime = next.time;
			numDone++;

			// Update tasks that must be finished.
			for (int i=0; i<n; i++) {

				if (dependencies[next.index][i] == 'Y') {
					curDegrees[i]--;

					// We can throw this into the queue now.
					if (curDegrees[i] == 0 && !used[i]) {
						used[i] = true;
						tasks.offer(new pair(i,curTime+times[i]));
					}
				}
			}
		}

		return curTime;
	}
}

class pair implements Comparable<pair> {

	public int index;
	public int time;

	public pair(int i, int t) {
		index = i;
		time = t;
	}

	public int compareTo(pair other) {
		return this.time - other.time;
	}
}