#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

string s, ans[3];
set<string> ses;
int res;

vector<string> change(string s){
	vector<string> vs;
	string t;
	REP(i, t.size() - 1){
		t = s;
		if (t[i] != t[i + 1]){
			if (t[i] == 'r'){
				if (t[i + 1] == 'g') t[i] = t[i + 1] = 'b';
				else t[i] = t[i + 1] = 'g';
			}
			else if (t[i] == 'g'){
				if (t[i + 1] == 'r')t[i] = t[i + 1] = 'b';
				else t[i] = t[i + 1] = 'r';
			}
			else{
				if (t[i + 1] == 'r')t[i] = t[i + 1] = 'g';
				else t[i] = t[i + 1] = 'r';
			}
			if (ses.find(t) == ses.end()){
				ses.insert(t);
				vs.push_back(t);
			}
		}
	}
	return vs;
}

void solve(string s){
	bool f = 1;
	queue<string> que;

	que.push(s);
	ses.insert(s);

	int k = que.size(), co = -1;

	for (int j = 0; j < k;j++){
		vector<string> vs;
		string t = que.front();

		//cout << "!" << t << endl;
		//if (f){
		//	cout << "!";
		//	REP(i, 3){
		//		if (t == ans[i]){
		//			cout << "!";
		//			cout << t << endl;
		//			f = 0;
		//		}
		//	}
		//}

		//cout << t << endl;
		//cout << "res ; " << res << endl;
		//cout << "j : " << j << endl;

		que.pop();
		vs = change(t);
		REP(i, vs.size()){
			que.push(vs[i]);
			/*cout << vs[i] << " ";*/
		}
		//cout << endl;

		if (j == k - 1){
			j = -1;
			k = que.size();
			res++;
		}
		/*cout << res << endl;*/

		if (f){
			REP(i, 3){
				if (find(ALL(vs), ans[i]) != vs.end()){
					//cout << "!";
					//cout << t << endl;
					//cout << "!";
					if (res == 1) cout << res << endl;
					else cout << res + 1 << endl;
					
					f = 0;
					break;
				}
			}
		}
		if (!f)break;
	}

	if (f)cout << "NA" << endl;
}

int main(){
	while (cin >> s){
		if (s == "0")break;
		ans[0] = ans[1] = ans[2] = "";
		REP(i, s.size()){
			ans[0] += 'r';
			ans[1] += 'g';
			ans[2] += 'b';
		}
		if (ans[0] == s || ans[1] == s || ans[2] == s){
			cout << 0 << endl;
			continue;
		}
		res = 0;
		solve(s);
	}
}