WORM

Partychen discover a strange worm in ECNU.The worm is too laze so it spends most of his life in sleep,the only way to wake it up is turn the worm's body into the same color. This worm’s body consist of N body sections, each body section could only be three kinds of colors: red (r), green (g), blue (b) . This worm's body color could change with the following two rules:
1:two adjacent section with different colors can change into another at the same time, such as rg could be bb,bg could be rr etc.
2: only one change could happen in the worm’s body per second.
Illustration below shows a series change in two seconds:

Now Partychen want you to tell him how long it required to wake up the strange worm at least.

The first line of input contains one integer N( N<=200),specifying the number of test cases to follow.The following N lines each line contain a series characters denotes the color status of the worm’s body.’r’,’g’,’b’ represents “red”,”‘green”,”blue” respectively.there are no extra spaces or blanks in the characters and the total length of each line is at most 10.

Output one line each case.if there is no way to wake up the strange worm output “No solution!”,otherwise output the smallest total time to do so.

8
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr

5
7
1
6
No solution!
8
0
4

2009 Multi-University Training Contest 18 - Host by ECNU