// Arup Guha
// 3/9/2020
// Solution to 2020 UCF HS Contest Problem: Why Don't We Use Giant Fans to Deal With Hurricanes?

import java.util.*;

public class winds {

	public static int n;
	public static char[][] grid;
	
	// Directions pieces can move.
	final public static int[] DX = {-1,0,0,1};
	final public static int[] DY = {0,-1,1,0};
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
		
			// Get grid.
			n = stdin.nextInt();
			grid = new char[n][];
			for (int i=0; i<n; i++)
				grid[i] = stdin.next().toCharArray();
		
			// Ta da!
			System.out.println(bfs());
		}
	}
	
	public static int bfs() {
	
		// Queue for BFS.
		LinkedList<Long> q = new LinkedList<Long>();
		
		// Store distances here. The key is the mask. The mask stores where the aliens are. 
		// The mapped value is the fewest number of moves to get to that state.
		// At most there are 64 squares in the middle where there could be aliens, so a long just works.
		// In my methods below, I explain how I store my mask.
		HashMap<Long,Integer> dist = new HashMap<Long,Integer>();
		
		// Starting mask.
		long mask = getMask();
		
		// Mark the distance and start up the queue.
		dist.put(mask, 0);
		q.offer(mask);
		
		// Start the BFS.
		while (q.size() > 0) {
		
			long curM = q.poll();
			
			// Try moving the aliens in each of the 4 possible directions.
			for (int i=0; i<DX.length; i++) {
				
				// Our new state.
				long nextM = getNextMask(curM, i);
				
				// Add to bfs.
				if (!dist.containsKey(nextM)) {
					dist.put(nextM, dist.get(curM)+1);
					q.offer(nextM);
					
					// Mask of 0 means no aliens, so return this distance.
					if (nextM == 0) return dist.get(nextM);
				}
			}
		}
		
		// Should never get here.
		return -1;
	}
	
	// Returns the mask of the initial state.
	public static long getMask() {
	
		long res = 0;
		
		// Go through each grid square in the middle.
		for (int i=1; i<n-1; i++)
			for (int j=1; j<n-1; j++)
				
				// If there is an alien, mark a 1 in this bit. My bit formula is using (1,1) as (0,0)
				// and then doing 0 to n-3 on row 1, n-2 to 2*(n-2)-1 on row 2 and so forth.
				if (grid[i][j] == 'A')
					res |= (1L <<( (i-1)*(n-2) + (j-1) ));
				
		// This is our mask.
		return res;
	}	
	
	public static long getNextMask(long curM, int dir) {
	
		long newM = 0;
		
		// Go thorugh each square of the mask.
		for (int i=0; i<(n-2)*(n-2); i++) {
			
			// I have an alien at location i.
			if (((1L<<i) & curM) != 0) {
			
				// 0 based location in inside of grid.
				// (nx, ny) is where the wind blows this alien.
				int nx = i/(n-2) + DX[dir];
				int ny = i%(n-2) + DY[dir];
				
				// If the new square isn't water, we add it to the new mask.
				if (grid[nx+1][ny+1] != 'W') 
					newM |= (1L<<(nx*(n-2)+ny));
			}
		}
		return newM;
	}
}