#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int res[11][180000];

int p(int n){
	if(n==0) return 1;
	return 3*p(n-1);
}

priority_queue<pint,vector<pint>,greater<pint> > bfs;
int i;

void g(pint a){
	int j;
	for(j=0;j<i-1;j++){
		if(a.second%p(j+1)/p(j)==a.second%p(j+2)/p(j+1)){
			int k=a.second%p(j+1)/p(j);
			int l=a.second;
			l-=k*p(j)+k*p(j+1);
			if(k==0){
				bfs.push(mp(a.first+1,l+p(j)+2*p(j+1)));
				bfs.push(mp(a.first+1,l+2*p(j)+p(j+1)));
			}
			if(k==1){
				bfs.push(mp(a.first+1,l+2*p(j+1)));
				bfs.push(mp(a.first+1,l+2*p(j)));
			}
			if(k==2){
				bfs.push(mp(a.first+1,l+p(j+1)));
				bfs.push(mp(a.first+1,l+p(j)));
			}
		}
	}
	return;
}

int main() {
	memset(res,-1,sizeof(res));
	for(i=2;i<=10;i++){
		int j,k=0;
		while(!bfs.empty())bfs.pop();
		for(j=0;j<i;j++)k+=p(j)*0;
		res[i][k]=0;
		g(mp(0,k));
		k=0;
		for(j=0;j<i;j++)k+=p(j)*1;
		res[i][k]=0;
		g(mp(0,k));
		k=0;
		for(j=0;j<i;j++)k+=p(j)*2;
		res[i][k]=0;
//cout<<k<<endl;
		g(mp(0,k));
		while(!bfs.empty()){
			pint buf;
			buf=bfs.top();
			bfs.pop();
//cout<<buf.first<<" "<<buf.second<<endl;
			if(res[i][buf.second]!=-1&&res[i][buf.second]<=buf.first)continue;
			res[i][buf.second]=buf.first;
			g(buf);
		}
	}
//for(i=2;i<=10;i++){
//	int j;
//	for(j=0;j<p(i);j++){
//		int l;
//		for(l=0;l<i;l++){
//			if(j/p(l)%3==0)cout<<"r";
//			if(j/p(l)%3==1)cout<<"b";
//			if(j/p(l)%3==2)cout<<"g";
//		}
//		cout<<" "<<res[i][j]<<endl;
//	}
//}
	string str;
	while(cin>>str,str!="0"){
		int k=0;
		int j;
		for(j=0;j<str.size();j++){
			if(str[j]=='r')k=k*3+0;
			if(str[j]=='b')k=k*3+1;
			if(str[j]=='g')k=k*3+2;
		}
		if(res[str.size()][k]>=0)cout<<res[str.size()][k]<<endl;
		else cout<<"NA\n";
	}
	return 0;
}