#include<iostream>
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<set>
#include<string>
#include<queue>
#include<map>

using namespace std;


int main(){



	string start_str;

	cin >> start_str;

	do{

		int ans = -1;

		queue< pair<int, string> > que;	//待ち行列 

		set<string> check_str;

		que.push(make_pair(0 , start_str));
		while (que.size()){

			string str;
			string sstr;	//色が変わったとき用

			int TIME = que.front().first;
			str = que.front().second;	//キューの先頭にある要素を取り出す
			que.pop();					//キューからポップする
			for (int i = 0; i < str.size() - 1; i++){
				if (str[i] != str[i + 1]){
					sstr = str;
					if (str[i] != 'r' && str[i + 1] != 'r'){
						sstr[i] = 'r'; sstr[i + 1] = 'r';
					}
					else if (str[i] != 'b' && str[i + 1] != 'b'){
						sstr[i] = 'b'; sstr[i + 1] = 'b';
					}
					else{
						sstr[i] = 'g'; sstr[i + 1] = 'g';
					}

					//cout << "TIME: " << TIME + 1 << "sstr: " << sstr << endl;

					if (sstr == start_str){	//変化した状態とスタートの状態が同じであったら
						continue;
					}
					else if (check_str.find(sstr) != check_str.end()){
						continue;
					}

					for (int j = 0; j < sstr.size() - 1; j++){
						if (sstr[j] != sstr[j + 1]){
							check_str.insert(sstr);
							que.push(make_pair(TIME + 1, sstr));	//make_pairは標準
							break;
						}

						if (j == sstr.size() - 2){	//一色に染まってたら
							ans = TIME + 1;
							i = str.size();
							while (!que.empty())
								que.pop();

						}

					}

				}
			}
		}

		if (ans == -1){
			for (int i = 0;i < start_str.size() - 1;i++){
				if (start_str[i] != start_str[i + 1]){
					cout << "NA" << endl;
					break;
				}

				if (i == start_str.size() - 2 ){
					cout << "0" << endl;
				}
			}
			
		}
		else{
			cout << ans << endl;
		}

		cin >> start_str;
	} while (start_str != "0");


	return 0;
}