#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef pair<string, int> P;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	while(cin >> s, s != "0") {
		int n = s.size();
		string R = string(n, 'r');
		string B = string(n, 'b');
		string G = string(n, 'g');

		map<string, int> m;
		m[s] = 0;
		queue<P> q;
		q.push({ s, 0 });
		while(q.size()) {
			s = q.front().first;
			int d = q.front().second;
			q.pop();
			if(m[s] < d) continue;
			//cout << s << endl;
			bool flag = false;
			for(int i = 0; i < n - 1; i++) {
				string ns = s;
				if(s[i] == 'r' && s[i + 1] == 'b' || s[i] == 'b' && s[i + 1] == 'r') ns[i] = ns[i + 1] = 'g';
				else if(s[i] == 'g' && s[i + 1] == 'b' || s[i] == 'b' && s[i + 1] == 'g') ns[i] = ns[i + 1] = 'r';
				else if(s[i] == 'r' && s[i + 1] == 'g' || s[i] == 'g' && s[i + 1] == 'r') ns[i] = ns[i + 1] = 'b';
				if(ns != s && m.count(ns) == 0) {
					m[ns] = d + 1;
					q.push({ ns, d + 1 });
					if(ns == R || ns == B || ns == G) { flag = true; break; }
				}
			}
			if(flag) break;
		}

		int ans = 1e9;
		if(m.count(R)) ans = min(ans, m[R]);
		if(m.count(B)) ans = min(ans, m[B]);
		if(m.count(G)) ans = min(ans, m[G]);
		if(ans != 1e9) {
			cout << ans << endl;
		}
		else {
			cout << "NA" << endl;
		}
	}
}