Problem Name: Mysterious Insect
Problem Description: Dr. A of Aizu Laboratory of Biological Science discovered a mysterious insect on a certain southern island. The shape is slender like a caterpillar, but because one body segment is shaped like a ball, it looks like a beaded ball connected by a thread. The strange thing was that there were various variations in the color of the body, and there were insects whose body color changed as time passed. Although the color of any insect body segment seems to be limited to either red, green or blue, the color of the body segment changes every second, and sometimes all body segments become the same color and settle down, while other times the color continues to change forever, no matter how long you wait.
As we investigated, we found that normally all body segments have the same color, but after being excited by something, we found that the color of the body segments changes on its own. Once the color of the body segment changes, it was found that the color will continue to change until all body segments become the same color again.
Dr. A caught many of these insects and excited them to observe the changing colors with interest, but eventually he noticed a rule in the way the color changes during the color change. The following is the rule he noticed:
The color changes only one pair of adjacent differently colored body segments, and the colors of other body segments do not change. However, if there are multiple such pairs, it is impossible to predict which pair will change color.
Such a pair changes color to a color that is not either of the two colors of the two body segments (for example, when a green and red body segment are adjacent, they change to blue at the same time).
The above figure shows the changes in the color of the insect up to 2 seconds. Let's assume that there is an insect with the color shown in the upper row of the figure. At this time, there are three pairs of adjacent differently colored body segments, so after 1 second, it will change to one of the three colors arranged in the middle row. When it changes like the left two in the middle row after 1 second, it can be changed to all the body segments being green after 2 seconds (the second from the left in the bottom row of the figure). On the other hand, when it changes like the rightmost one in the middle row after 1 second, all body segments will not change to the same color after 2 seconds.
Dr. A decided to predict whether it is possible for all body segments of the insect in front of him to become the same color, and if so, to create a program that outputs the shortest time it will take to do so in seconds. However, if it is impossible to become the same color, please output "NA" (capital letters only). The arrangement of the colors of the body segments of the insect is represented by a string consisting of 2 to 10 characters of r (red), g (green), and b (blue).
Input
The input is a sequence of multiple data sets. The end of the input is indicated by a single zero line. For each dataset, one string representing the body segments of the insect is given on one line.
The number of data sets does not exceed 100.
Output
For each dataset, output the minimum time (in seconds) required for all body segments to become the same color or "NA" on one line.
Sample Input
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0
Output for the Sample Input
5
7
1
6
NA
8
0
4