#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<vector<int>, int>mp;

map<char, int>chmp;
int getans(vector<int> st,int m) {
	if (mp.find(st) != mp.end())return  mp[st];
	else {
		if (m >= 1000)return 1e8;
		if (all_of(st.begin(), st.end(), [=](const int n) {return n == st[0]; }))return mp[st] = 0;
		mp[st] = 1e8;
		int ans = 1e8;
		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];
				ans = min(ans, getans(nowst,m+1) + 1);
			}
		}
		return mp[st] = ans;
	}
}

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]);
		}
		int ans = getans(nums,0);
		if (ans > 1e7) {
			cout << "NA" << endl;
		}
		else {
			cout << ans << endl;
		}
	}
	return 0;
}