#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define EPS 1e-8
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define MAX_v 100
typedef long long ll;
typedef unsigned long long ull;
typedef pair<string,int> P;
int main(){
	string s;
	while(cin >> s , s!="0"){
		int len = s.size();
		int check = -1;
		queue<P> Q;
		Q.push(P(s,0));
		vector<string> vis;
		while( Q.size() ){
			P p = Q.front();Q.pop();
			string tmp = p.first;
			string k = p.first;
			//cout << "D:" << tmp << endl;
			bool f = false;
			rep(i,len-1){
				if(tmp[i] != tmp[i+1]){f = true;break;}
			}
			if(!f){check = p.second;break;}
			if(find(vis.begin(),vis.end(),tmp) != vis.end())continue;
			vis.push_back(tmp);
			rep(i,len-1){
				if(tmp[i] < tmp[i+1]){
					swap(k[i],k[i+1]);
				}
				if(k[i]=='r'&&k[i+1]=='g'){k[i]=k[i+1]='b';Q.push(P(k,p.second+1));}
				else if(k[i]=='r'&&k[i+1]=='b'){k[i]=k[i+1]='g';Q.push(P(k,p.second+1));}
				else if(k[i]=='g'&&k[i+1]=='b'){k[i]=k[i+1]='r';Q.push(P(k,p.second+1));}
				k = p.first;
			}
		}
		(check != -1) ? printf("%d\n",check) : puts("NA");
	}
	return 0;
}