#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

char change(char a, char b) {
	switch(a) {
	case 'r':
		return (b == 'g' ? 'b' : 'g');
	case 'g':
		return (b == 'r' ? 'b' : 'r');
	case 'b':
		return (b == 'r' ? 'g' : 'r');
	}
}

bool ok(string s) {
	REP(i, s.size()-1) {
		if(s[i] != s[i+1]) {
			return false;
		}
	}
	return true;
}

struct state {
	string s;
	int t;
	state(string s, int t) : s(s), t(t) {};
};

int main() {
	string s;
	while(cin >> s, s != "0") {
		queue<state> Q;
		Q.push(state(s, 0));
		set<string> S;
		S.insert(s);		
		int ans = -1;
		while(!Q.empty()) {
			state st = Q.front();
			Q.pop();
			string cs = st.s;

			if(ok(cs)) {
				ans = st.t;
				break;
			}

			REP(i, cs.size()-1) {
				if(cs[i] != cs[i+1]) {
					string ns = cs;
					char a = cs[i];
					char b = cs[i+1];
					ns[i] = change(a, b);
					ns[i+1] = change(a, b);

					if(S.find(ns) == S.end()) {
						S.insert(ns);
						Q.push(state(ns, st.t+1));
					}
				}
			}
		}

		if(ans != -1) {
			cout << ans << endl;
		} else {
			cout << "NA" << endl;
		}
	}

	return 0;
}