#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
using namespace std;

const int INF = 1e+9;
typedef pair<string, int> P;

int ans = 0;
int s_size;

string change(string s, int a, int b){
	if((s[a] == 'r' && s[b] == 'g') || (s[a] == 'g' && s[b] == 'r'))
		s[b] = s[a] = 'b';
	else if((s[a] == 'b' && s[b] == 'g') || (s[a] == 'g' && s[b] == 'b'))
		s[b] = s[a] = 'r';
	else
		s[b] = s[a] = 'g';
	
	return s;
}

int main() {
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	string str;
	while(cin >> str){
		if(str == "0")
			break;
		s_size = str.size();
		ans = INF;
		queue<P> que;
		map<string, bool> visited;
		que.push(P(str, 0));
		while(!que.empty()){
			P p = que.front();
			que.pop();
			string s = p.first;
			if(visited[s])
				continue;
			visited[s] = true;
			bool flag = false;
			for(int i = 0; i < s_size - 1; ++i){
				if(s[i] != s[i + 1])
					break;
				if(i == s_size - 2){
					ans = min(ans, p.second);
					flag = true;
					break;
				}
			}
			if(flag)
				continue;
			for(int i = 0; i < s_size - 1; ++i){
				if(s[i] != s[i + 1]){
					string t = change(s, i, i + 1);
					que.push(P(t, p.second + 1));
				}
			}
		}
		end:
		if(ans == INF)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
	return 0;
}