#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
typedef pair<string,int> P;
char color[3] = {'r','g','b'};
string com[3];
string str;
int len;
int bfs();

int main(){
	while(1){
		cin >> str;
		if(str == "0") break;
		len = str.size();
		for(int i=0;i<3;i++){
			com[i] = "";
			for(int j=0;j<len;j++){
				com[i] += color[i];
			}
		}
		int ans = bfs();
		if(ans == -1) cout << "NA" << endl;
		else cout << ans << endl;
	}
}

int bfs(){
	queue<P> que;
	que.push(P(str,0));
	map<string,int> dp;
	while(!(que.empty())){
		P p = que.front(); que.pop();
		string now = p.first;
		int cou = p.second;
		for(int i=0;i<3;i++){
			if(now == com[i]) return cou;
		}
		if(dp[now]) continue;
		dp[now] = 1;
		for(int j=0;j<len-1;j++){
			if(now[j] != now[j+1]){
				string tmp = now;
				for(int k=0;k<3;k++){
					if(tmp[j] != color[k] && tmp[j+1] != color[k]){
						tmp[j] = color[k];
						tmp[j+1] = color[k];
						break;
					}
				}
				que.push(P(tmp,cou+1));
			}
		}
	}
	return -1;
}