http://poj.org/problem?id=1681
//* @author:
import java.util.*;
public class Main {
static Scanner in = new Scanner(System.in);
static char[][] board;//���ڱ����ʼ״̬
static boolean[][] map;//ǽ�ڵ�״̬
static int cnt;//Ϳ��Ĵ���
static void click(int x, int y) {//Ϳ��x,y)���ĸ���
++cnt;
map[x][y] = !map[x][y];
if(x-1>=0) map[x-1][y] = !map[x-1][y];//����ĸ���
if(y-1>=0) map[x][y-1] = !map[x][y-1];//��ߵĸ���
if(x+1< map.length) map[x+1][y] = !map[x+1][y];//����ĸ���
if(y+1< map[x].length) map[x][y+1] = !map[x][y+1];//�ұߵĸ���
}
static int check(int s) {
cnt = 0;
for(int i=0; i!=map.length; ++i)//��ʼ״̬
for(int j=0; j!=map[i].length; ++j)
map[i][j] = board[i][j]=='w';
for(int i=0; i!=map[0].length; ++i)//ȷ����һ�еľ������
if((s&(1<< i))!=0)
click(0, i);
for(int i=1; i!=map.length; ++i)//Ϳ�ڶ��������һ��
for(int j=0;j!=map[i].length; ++j)
if(map[i-1][j]) click(i, j);
for(int j=0; j!=map[map.length-1].length; ++j)//������һ���Ƿ�ȫ�ǻ�ɫ
if(map[map.length-1][j]) return Integer.MAX_VALUE;
return cnt;
}
public static void main(String[] args) {
int t = in.nextInt();//���Դ���
while(t-->0) {
int n = in.nextInt();//���ӵĹ�ģ
board = new char[n][];
for(int i=0; i!=n; ++i) {
board[i] = in.next().toCharArray();
}
map = new boolean[n][n];
int ans = Integer.MAX_VALUE;
for(int i=0; i!=(1 << n); ++i) {//��һ����2^n�ֱ仯����ÿһ�ֱ仯����
ans = Math.min(ans, check(i));
}
if(ans< Integer.MAX_VALUE) System.out.println(ans);
else System.out.println("inf");
}
}
}