There is a n * n lowercase letter matrix, and I want you to modify this matrix, but I don't want to modify it too much. I want to make this matrix just contain exactly two different letters and what's more, any two lattices can't be same if they are neighboring. Now please tell me the least number of lattice need to be modify.

Input starts with an integer T(T <= 10) denoting the number test case.
For each test case, first line contains an integer n(1 <= n <= 500) denoting the size of matrix.
then n lines following, each line contains a string which length is n.

For each test case, print the least number of lattice need to be modify.