#include <bits/stdc++.h>
#define MAX 1002

using namespace std;

string s[MAX];
int n,tc;
int vis[MAX][MAX][3][3];
int dp[MAX][MAX][3][3];

int f(int i, int j, int cnt1, int cnt2)
{
	if ( i > j ) {
		if ( cnt1 == 0 && cnt2 == 0 ) return 0;
		return n + 1;
	}
	if ( i == j ) {
		int sz = (int)s[i].size();
		int idx1 = cnt1, idx2 = sz - cnt2 - 1;
		if ( idx1 > idx2 ) return n+1;
		int ans = n + 1;
		if ( cnt1 == 0 && cnt2 == 0 ) ans = 1;
		while ( idx1 < idx2 ) {
			if ( s[i][idx1] != s[i][idx2] ) return min(ans, n + 1);
			idx1++;
			idx2--;
		}
		return 0;
	}
	if ( vis[i][j][cnt1][cnt2] == tc ) return dp[i][j][cnt1][cnt2];
	vis[i][j][cnt1][cnt2] = tc;
	
	int ans = n + 1;
	
	if ( cnt1 == 0 ) ans = min(ans, 1 + f(i + 1, j, 0, cnt2));
	if ( cnt2 == 0 ) ans = min(ans, 1 + f(i, j - 1, cnt1, 0));
	
	int sz1 = (int)s[i].size();
	int sz2 = (int)s[j].size();

	if ( s[i][cnt1] == s[j][sz2-cnt2-1] ) {

		if ( cnt1 + 1 < sz1 && cnt2 + 1 < sz2 ) ans = min(ans, f(i, j, cnt1 + 1, cnt2 + 1));
		else if ( cnt1 + 1 < sz1 ) ans = min(ans, f(i, j - 1, cnt1 + 1, 0));
		else if ( cnt2 + 1 < sz2 ) ans = min(ans, f(i + 1, j, 0, cnt2 + 1));
		else ans = min(ans, f(i + 1, j - 1, 0, 0));

	}

	dp[i][j][cnt1][cnt2] = ans;
	return ans;

}

int main()
{
	int t;
	
	cin >> t;
	assert(t >= 1 && t <= 5);
	
	for ( tc = 1; tc <= t; tc++ ) {
		
		cin >> n;
		assert(n >= 1 && n <= 1000);

		for ( int i = 0; i < n; i++ ) {
			cin >> s[i];
			assert((int)s[i].size() <= 2);
			for ( int j = 0; j < (int)s[i].size(); j++ ) assert(s[i][j] >= 'a' && s[i][j] <= 'b');
		}
		
		cout << f(0, n - 1, 0, 0) << endl;
	
	}
	
	return 0;
}