#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;

typedef pair<string ,int> P;

int bfs(string str)
{
	map<string, int> m;
	queue<P> que;
	que.push(P(str,1));
	while(!que.empty())
	{
		P p = que.front();que.pop();
		if(m[p.first]) continue;//すでに数字が存在するときはやりなおし
		bool flag=true;
		for(int i=0;i<p.first.size()-1;++i){
			if(p.first[i] != p.first[i+1])
				flag = false;
		}
		if(flag) return p.second-1;
		m[p.first] = p.second;//重複をなくす
		for(int i=0;i<str.size()-1;++i){
			char c;
			if(p.first[i] == p.first[i+1])
				continue;
			if(p.first[i] != 'r' && p.first[i+1] != 'r')
				c = 'r';
			if(p.first[i] != 'g' && p.first[i+1] != 'g')
				c = 'g';
			if(p.first[i] != 'b' && p.first[i+1] != 'b')
				c = 'b';
			string next = p.first;
			next[i] = next[i+1] = c;
			que.push(P(next,p.second+1));
		}
	}
	return -1;
}

int main(void)
{
	while(1){
		string str;
		cin >> str;
		if(str[0] == '0')
			return 0;
		int res = bfs(str);
		if(res >= 0)
			cout << res << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}