#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int cnt,ccnt = 0;
int len;
string s, ss, tmp;
int flag = 0;
int fflag=0;
char c;
vector<string> v_list;
pair<string,int> ps;
int main() {
	while (cin >> s) {
		if (s == "0") {
			break;
		}
		fflag=0;
		//v_list.push_back(s);
		len = s.length();
		queue<pair<string,int> > qq;
		qq.push(make_pair(s,0));
		while (!qq.empty()) {
			ps = qq.front();
			qq.pop();
			c = ps.first[0];

			ccnt=ps.second;
			flag = 0;
			//vector<int>::iterator cIter = std::find( v_list.begin(), v_list.end(), ps.first);

			if( (find( v_list.begin(), v_list.end(), ps.first)) != v_list.end() ){
				continue;
			}
			v_list.push_back(ps.first);

			for (int i = 1; i < len; i++) {
				if (c != ps.first[i]) {
					//cout<<ps.first[i]<<endl;//deb
					flag = 1;
					break;
				}
			}
			if (flag) {
				for (int i = 0; i < len - 1; ++i) {
					tmp = ps.first;
					if (ps.first[i] != ps.first[i+1]) {
						if (ps.first[i] != 'r' && ps.first[i+1] != 'r') {
							tmp[i] = 'r';
							tmp[i + 1] = 'r';
							//cout<<tmp<<endl;//deb
							qq.push(make_pair(tmp,ccnt+1));
						}
						if (ps.first[i] != 'g' && ps.first[i+1] != 'g' ){
							tmp[i] = 'g';
							tmp[i + 1] = 'g';
							//cout<<tmp<<endl;//deb
							qq.push(make_pair(tmp,ccnt+1));
						}
						if (ps.first[i] != 'b' && ps.first[i+1] != 'b') {
							tmp[i] = 'b';
							tmp[i + 1] = 'b';
							//cout<<tmp<<endl;//deb
							qq.push(make_pair(tmp,ccnt+1));
						}
					}
				}
			} else {
				cout << ccnt << endl;
				fflag=1;
				break;
			}
		}
		if(!fflag){printf("NA");cout<<endl;};
	}
	return 0;
}