#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	string s;
	char a[] = {'r','g','b'};
	set<string> u;
	queue< pair<string,int> > q;
	cin >> s;
	if(s == "0") break;
	u.insert(s);
	q.push( pair<string,int>(s,0));
	int ans = 0;
	while(!q.empty()){
	    s = q.front().first;
	    int v = q.front().second;
	    q.pop();
	    REP(i,s.size()-1){
		if(s[i] != s[i+1]){
		    string s1 = s;
		    char key;
		    REP(j,3){
			if(s[i] != a[j] && s[i+1] != a[j]){
			    key = a[j];
			}
		    }
		    s1[i] = key;
		    s1[i+1] = key;
		    if(u.find(s1) == u.end()){
			u.insert(s1);
			q.push(pair<string,int>(s1,v+1));
		    }
		}
	    }
	    bool flg = true;
	    REP(i,s.size()-1){
		if(s[i] != s[i+1] ) flg = false;
	    }
	    if(flg){
		cout << v << endl;
		break;
	    }else if(q.empty()){
		cout << "NA" << endl;
		break;
	    }
	}
    }
    return 0;
}