#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <climits>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> P;
static const int INF=1<<24;

string s;
string qf;
set<string> vis;

bool check(string a){
	char t=a[0];
	rep(i,a.size()){
		if(t!=a[i]) return false;
	}
	return true;
}

int main(){
	
	while(cin>>s,s[0]!='0'){
		//cout<<s<<endl;
		vis.clear();
		int ans=-1;
		queue<string> qu;
		if(check(s)){
			cout<<"0"<<endl;
			continue;
		}
		vis.insert(s);
		qu.push(s);
		bool f1=false;
		bool f2=false;
		bool f3=false;
		while(!qu.empty()){
			f1=false;
			f2=false;
			ans++;
			int qs=qu.size();
			rep(i,qs){
				qf=qu.front();
				qu.pop();
				rep(j,s.size()-1){
					if(qf[j]!=qf[j+1]){
						string tmp=qf;
						tmp[j] = tmp[j+1] = 'r'+'g'+'b'-qf[j]-qf[j+1];
						if(vis.find(tmp)==vis.end()){
							qu.push(tmp);
							vis.insert(tmp);
							f1=true;
							if(check(tmp)) f3=true;
						}
						f2=true;
					}
				}
			}
			if(f3) break;
		}
		if(f3) cout<<ans+1<<endl;
		else cout<<"NA"<<endl;
		
	}
	
	return 0;
}