#include <iostream>
#include <string>
#include <map>
#include <queue>

using namespace std;

typedef pair<string, int> P;

int main() {
	string s;
	while (cin >> s) {
		if (s == "0") {
			break;
		}
		map<string, int> mp;
		queue<P> q;
		q.push(P(s, 0));
		int count = -1;
		int sz = s.size();
		char cc = s[0];
		bool hantei = true;
		for (int i = 1; i < sz; i++) {
			if (s[i] != cc) {
				hantei = false;
				break;
			}
		}
		mp[s]++;
		if (hantei) {
			cout << 0 << endl; 
		} else {
			while (!q.empty()) {
				P aa = q.front();
				q.pop();
				string a = aa.first;
				for (int i = 0; i < sz-1; i++) {
					if (a[i] == a[i+1]) {
					} else {
						string b = a;
						if ((a[i] == 'r' && a[i+1] == 'g')||(a[i] == 'g' && a[i+1] == 'r')) {
							b[i] = b[i+1] = 'b';
						} else if ((a[i] == 'g' && a[i+1] == 'b')||(a[i] == 'b' && a[i+1] == 'g')) {
							b[i] = b[i+1] = 'r';
						} else {
							b[i] = b[i+1] = 'g';
						}
						//cout << b << endl;
						mp[b]++;
						if (mp[b] > 1) {
						} else {
							char ccb = b[0];
							bool hantei2 = true;
							for (int i = 1; i < sz; i++) {
								if (b[i] != ccb) {
									hantei2 = false;
									break;
								}
							}
							if (hantei2) {
								count = aa.second+1;
								break;
							} else {
								q.push(P(b, aa.second+1));
							}
						}
					}
				}
				if (count != -1) {
					break;
				}
			}
			if (count != -1) {
				cout << count << endl;
			} else {
				cout << "NA" << endl;
			}
		}
	}
	return 0;
}