A few kids are standing around an old tree playing a game. The tree is so huge that each kid can only see the kids close to him/her.

The game consists many �turns�. At the beginning of each turn of the game, a piece of paper is given to a randomly chosen kid. This kid writes the letter �B� if he is a boy or the letter �G� if a girl. Then he chooses a direction to pass the paper (clockwise or counter-clockwise), and gives the paper to his neighbor in that direction. The kid getting the paper writes down his sex too, and gives the paper to his neighbor in the same direction. In this way, the paper goes through the kids one by one, until one kid stops passing the paper and announces the end of this turn.

For example, there are five kids around the tree, and their genders are shown in Figure-1. The paper first goes to Kid1, after writing a �B� he passes it to Kid2, and Kid2 to Kid3. After Kid3 writes down a �G�, she ends up this turn, and we get the paper with a string �BBG�.

After N turns, we get N pieces of paper with strings of �B�s and/or �G�s. One of the kids will get all these papers, and has to figure out at least how many kids are around the tree playing the game. It's known that there are at least two kids. Please write a program to help him.

Input 

There are several test cases. Each case starts with a line containing an integer N, the number of papers (2 ≤ N ≤ 16). Each of the following N lines contains a string on a paper, which is a nonempty string of letter �B�s and/or �G�s. Each string has no more than 100 letters.

A test case of N = 0 indicates the end of input, and should not be processed.

Output 

For each test case, output the least possible number of kids in a line.

Sample Input 

3
BGGB
BGBGG
GGGBGB
2
BGGGBBBGG
GBBBG
0

Sample Output 

9
6

先考慮單一資訊具有多圈的情況，使用 KMP 去進行檢測來加快速度。

狀態 O(2^16*16*2)，轉移次數共計 2^16*16*2*16 = 33554432。
使用 KMP 求 maximum suffix matching，否則建圖就需要 16*16*100*100 = 2560000。
使用 KMP 降至 16*16*100 = 25600。
建圖完之後，挑一個最長的出來當起點，使用 TSP 的 DP+bitmask。
如果答案等於最長的那個點，則開始進行自繞測試。
自繞測試最慘為 100*16*100*100 = 16000000。
用 KMP 降至 100*16*100 = 1600000。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
void kmpTable(char s[], int P[]) {
    int i, j;
    P[0] = -1, i = 1, j = -1;
    while(s[i]) {
        while(j >= 0 && s[j+1] != s[i])
            j = P[j];
        if(s[j+1] == s[i])
            j++;
        P[i++] = j;
    }
}
int suffixMatching(char A[], char B[], int la, int lb) { // B in A
	static int P[305];// modify KMP matching.
    int i, j, Alen, Blen;
    Alen = la, Blen = lb;
    kmpTable(B, P);
    for(i = 0, j = -1; i < Alen; i++) {
        while(j >= 0 && B[j+1] != A[i])
            j = P[j];
        if(B[j+1] == A[i])    j++;
        if(j == Blen-1)
            return j;
    }
    return j;
}
int cost[16][2][16][2];
int lapped[16][2][16][2];
int dp[1<<16][16][2], dp_st;
int dfs(int state, int last, int inv, int n) {
	int &ret = dp[state][last][inv];
	if(ret != -1)	return ret;
	int i;
	for(i = 0; i < n; i++) {
		if((state>>i)&1) {
			if(cost[last][inv][i][0] == 0 || cost[last][inv][i][1] == 0)
				state ^= (1<<i);
		}
	}	
	if(state == 0) {;
		if(dp_st != last)
			return -lapped[last][inv][dp_st][0];
		return 0;
	}
	ret = 0xfffffff;
	for(i = 0; i < n; i++) {
		if((state>>i)&1) {
			ret = min(ret, dfs(state^(1<<i), i, 0, n)+cost[last][inv][i][0]);
			ret = min(ret, dfs(state^(1<<i), i, 1, n)+cost[last][inv][i][1]);
		}
	}
	return ret;
}
int n;
int i, j, k;
int p, q, r;
char paper[16][2][255];
int paperlen[16];
int special_check() {
	char buf[305];
	int i, j;
	for(i = 1; i < paperlen[dp_st]; i++) {
		int mm = 2*paperlen[dp_st]+2;
		for(j = 0; j < mm; j++)
			buf[j] = paper[dp_st][0][j%(i+1)];
		buf[mm] = '\0';
		int ok = 1;
		for(j = 0; j < n && ok; j++) {
			int flag = 0, t;
			t = suffixMatching(buf, paper[j][0], mm, paperlen[j]);
			if(t == paperlen[j]-1)
				continue;
			t = suffixMatching(buf, paper[j][1], mm, paperlen[j]);
			if(t == paperlen[j]-1)
				continue;
			ok = 0;
		}
		if(ok)
			return i+1;
	}
	return 0xfffffff;
}
int main() {
	while(scanf("%d", &n) == 1 && n) {
		for(i = 0; i < n; i++) {
			scanf("%s", paper[i][0]);
			paperlen[i] = strlen(paper[i][0]);
			for(j = paperlen[i]-1, k = 0; j >= 0; j--, k++)
				paper[i][1][j] = paper[i][0][k];
			paper[i][1][paperlen[i]] = '\0';
		}
		for(i = 0; i < n; i++) {
			for(p = 0; p < 2; p++) {
				for(j = 0; j < n; j++) {
					for(q = 0; q < 2; q++) {
						int pos = suffixMatching(paper[i][p], paper[j][q], paperlen[i], paperlen[j]);
						cost[i][p][j][q] = paperlen[j]-pos-1;
						lapped[i][p][j][q] = pos+1;
					}
				}
			}
		}
		memset(dp, -1, sizeof(dp));
		dp_st = 0;
		for(i = 0; i < n; i++) {
			if(paperlen[i] > paperlen[dp_st])
				dp_st = i;
		}
		int ret = special_check();
		if(ret != 0xfffffff) {
			printf("%d\n", ret);
			continue;
		}
		ret = dfs((1<<n)-1-(1<<dp_st), dp_st, 0, n)+paperlen[dp_st];
		printf("%d\n", ret);
	}
	return 0;
}