#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;

int main(){
	string str,tmp,s;
	bool f;
	while(cin >> str){
		queue<string> que;
		map<string,int> m;
		if(str == "0") break;
		que.push(str);
		while(!que.empty()){
			f = true;
			s = tmp = que.front();
			que.pop();
			for(int i = 0;i < s.length()-1;++i){
				if(s[i] != s[i+1]) f = false; 
			}
			if(f) break;
			for(int i = 0;i < tmp.length()-1;++i){
				if(tmp[i] == 'r'){
					if(tmp[i+1] == 'b') tmp[i] = tmp[i+1] = 'g';
					else if(tmp[i+1] == 'g') tmp[i] = tmp[i+1] = 'b';
				}
				else if(tmp[i] == 'b'){
					if(tmp[i+1] == 'r') tmp[i] = tmp[i+1] = 'g';
					else if(tmp[i+1] == 'g') tmp[i] = tmp[i+1] = 'r';
				}
				else if(tmp[i] == 'g'){
					if(tmp[i+1] == 'r') tmp[i] = tmp[i+1] = 'b';
					else if(tmp[i+1] == 'b') tmp[i] = tmp[i+1] = 'r';
				}
				if(!m.count(tmp)) {
					que.push(tmp);
					m[tmp] = m[s] + 1;
				}
				tmp = s;
			}
		}
		if(f) cout << m[s] << endl;
		else cout << "NA" << endl;
		m.clear();
		while(!que.empty()) que.pop();
	}
	return 0;
}