#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()
 
#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<vi> vvi;
 
const int IMAX=((1<<30)-1)*2+1;
const int INF=100000000;
const double EPS=1e-10;
//int mod=1000000007
 
string str;
bool f(string s){
	for(int i = 1; i <s.size(); i++){
		if(s[i] != s[i-1]) return false;
	}
	return true;
}

string calc(int i,string s){
	string ret = s;
	if(s[i] != s[i+1]){
		if((ret[i]=='g' && ret[i+1] == 'r') ||(ret[i]=='r' && ret[i+1] == 'g')) ret[i] = ret[i+1] ='b';
		else if((ret[i]=='b' && ret[i+1] == 'r') ||(ret[i]=='r' && ret[i+1] == 'b')) ret[i] = ret[i+1] ='g';
		else if((ret[i]=='g' && ret[i+1] == 'b') ||(ret[i]=='b' && ret[i+1] == 'g')) ret[i] = ret[i+1] ='r';
	}
	return ret;
}

int main(){
	while(cin>>str){
		if(str == "0") break;
		set<string> s;
		queue<pair<string,int> > q;
		int ans = 0;
		pair<string,int> p;
		s.insert(str);
		q.push(pair<string,int>(str,0));
		bool flag = false;
		while(!q.empty()){
			p = q.front();
			q.pop();
			if(f(p.fi)) {
				ans = p.se;
				flag = true;
				break;
			}
			for(int i = 0; i< str.size()-1; i++){
				if(!s.count(calc(i,p.fi))){
					q.push(pair<string,int>(calc(i,p.fi),p.se+1));
					s.insert(calc(i,p.fi));
				}
			}
		}
		if(flag) cout<<ans<<endl;
		else cout<<"NA"<<endl;
	}
}