#include <iostream>
#include <string>
#include <queue>
#include <set>

using namespace std;

typedef pair<string, int> P;

bool hantei (string a) {
	for (int i = 1; i < a.size(); i++) {
		if (a[0] == a[i]) {
		} else {
			return false;
		}
	}
	return true;
}

int main() {
	string a;
	string abc = "rgb";
	while (getline(cin, a)) {
		if (a[0] == '0') {
			break;
		}
		queue<P> q;
		q.push(P(a, 0));
		bool han = true;
		int t;
		set<string> s;
		if (hantei(a)) {
			han = false;
			cout << 0 << endl;
		}
		while (!q.empty()) {
			P p = q.front();
			q.pop();
			string pp = p.first;
			for (int i = 0; i < pp.size()-1; i++) {
				if (!han) {
					break;
				}
				if (pp[i] == pp[i+1]) {
				} else {
					string qq = pp;
					int v, w;
					for (int j = 0; j < abc.size(); j++) {
						if (abc[j] == pp[i]) {
							v = j;
						}
						if (abc[j] == pp[i+1]) {
							w = j;
						}
					}
					qq[i] = qq[i+1] = abc[3-(v+w)];
					if (hantei(qq)) {
						han = false;
						cout << p.second+1 << endl;
						break;
					}
					if (s.find(qq) == s.end()) {
						s.insert(qq);
						q.push(P(qq, p.second+1));
					}
				}
			}
		}
		if (han) {
			cout << "NA" << endl;
		}
	}
	return 0;
}