本题没有可用的提交语言。

描述

几个孩子围绕着一棵大树玩游戏。这棵树非常大，以至于每个孩子只能看到他/她附近的孩子。

游戏由多个“回合”组成。在每个回合的开始，一张纸随机交给一个孩子。这个孩子如果是个男孩，就写下一个字母“B”，如果是女孩，就写下一个字母“G”。然后他选择一个方向传递纸张（顺时针或逆时针），并将纸张交给该方向上的邻居。拿到纸的孩子也写下自己的性别，然后将纸张传递给同一方向上的邻居。这样，纸张依次经过每个孩子，直到某个孩子决定停止传递纸张并宣布这一回合结束。

例如，有五个孩子围绕着树，他们的性别如图1所示。纸张首先传到Kid1手中，他写下“B”后传给Kid2，Kid2再传给Kid3。Kid3写下“G”后结束这一回合，我们得到一张写有“BBG”的纸。

经过 $N$ 个回合后，我们得到了 $N$ 张写有“B”和/或“G”的字符串的纸。其中一个孩子会拿到所有这些纸，并需要推断出至少有多少个孩子围绕着树玩游戏。已知至少有两个孩子。请编写一个程序来帮助他。

输入

输入包含多个测试用例。每个测试用例的第一行包含一个整数 $N$，表示纸张的数量（$2 \leq N \leq 16$）。接下来的 $N$ 行每行包含一张纸上的字符串，该字符串是由字母“B”和/或“G”组成的非空字符串。每个字符串最多包含100个字母。

一个测试用例 $N = 0$ 表示输入结束，不应被处理。

输出

对于每个测试用例，输出一行，表示最少可能的孩子数量。

输入数据 1

3  
BGGB  
BGBGG  
GGGBGB  
2  
BGGGBBBGG  
GBBBG  
0

输出数据 1

9  
6

来源

北京2004