Description

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.

3
BGGB
BGBGG
GGGBGB
2
BGGGBBBGG
GBBBG
0

9
6

Source

Beijing 2004