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

int main(){
	string s;
	while(1){
		map<string,bool> used;
		cin >> s;
		if(s == "0") break;
		queue<string> que;
		que.push(s);
		for(int i = 0;;i++){
			int siz = que.size();
			if(!siz){
				cout << "NA" << endl;
				break;
			}
			for(int j = 0;j < siz;j++){
				s = que.front();que.pop();
				if(used[s]) continue;
				used[s] = true;
				char c = s[0];
				bool flag = true;
				for(int k = 1;k < s.length();k++){
					if(s[k] != c) flag = false;
				}
				if(flag){
					cout << i << endl;
					goto end;
				}
				for(int k = 0;k < s.length() - 1;k++){
					if(s[k] != s[k + 1]){
						string t = s;
						if(s[k] != 'g' && s[k + 1] != 'g'){
							t[k] = 'g';
							t[k + 1] = 'g';
							que.push(t);
						}
						else if(s[k] != 'r' && s[k + 1] != 'r'){
							t[k] = 'r';
							t[k + 1] = 'r';
							que.push(t);
						}
						else{
							t[k] = 'b';
							t[k + 1] = 'b';
							que.push(t);
						}
					}
				}
			}
		}
		end:
		continue;
	}
	return 0;
}