#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


map<char, int>chmp;

int main() {
	chmp['r'] = 0;
	chmp['g'] = 1;
	chmp['b'] = 2;
	while (1) {

		string st; cin >> st;
		if (st == "0")break;
		vector<int>nums;
		for (auto c : st) {
			nums.emplace_back(chmp[c]);
		}

		map<vector<int>, int>mp;
		queue<pair<int,vector<int>>>que;
		que.push(make_pair(0,nums));
		int ans = 1e8;
		while (!que.empty()) {
			auto p(que.front());
			que.pop();
			if (mp.find(p.second) != mp.end())continue;
			mp[p.second];
			if (all_of(p.second.begin(), p.second.end(), [=](const int n) {return n == p.second[0]; })) {
				ans = p.first;
				break;
			}
			vector<int>st(p.second);
			for (int i = 0; i < st.size() - 1; ++i) {
				if (st[i] != st[i + 1]) {
					vector<int>nowst(st);
					nowst[i] = 3 - st[i] - st[i + 1];
					nowst[i + 1] = 3 - st[i] - st[i + 1];
					que.push(make_pair(p.first + 1, nowst));
				}
			}
		}
		if (ans > 1e7) {
			cout << "NA" << endl;
		}
		else {
			cout << ans << endl;
		}
	}
	return 0;
}