#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int clr_int(string str)
{
	int v = 0;
	int r = 1;
	for(int i = 0;i < str.size();i++)
	{
		switch(str[i])
		{
			case 'g':
			v += r;
			break;
			case 'b':
			v += r*2;
			break;
		}
		r *= 3;
	}
	return v;
}
string int_clr(int v,int l)
{
	string str;
	for(int i = 0;i < l;i++)
	{
		int r = v % 3;
		switch(r)
		{
			case 0:
			str += "r";
			break;
			case 1:
			str += "g";
			break;
			case 2:
			str += "b";
			break;
		}
		v /= 3;
	}
	return str;
}

vector<vector<int>> makeG(int l)
{
	auto grh = vector<vector<int>>();
	int r = 1;
	for(int i = 0;i < l;i++)
	{
		r *= 3;
	}
	for(int i = 0;i < r;i++)
	{
		auto str = int_clr(i,l);
		auto ary = vector<int>();
		for(int j = 0;j < (l-1);j++)
		{
			if(str[j] != str[j+1])
			{
				auto scp = string(str);
				switch(str[j])
				{
					case 'r':
					scp[j] = scp[j+1] = (str[j+1] == 'g')?'b':'g';
					ary.push_back(clr_int(scp));
					break;
					case 'g':
					scp[j] = scp[j+1] = (str[j+1] == 'b')?'r':'b';
					ary.push_back(clr_int(scp));
					break;
					case 'b':
					scp[j] = scp[j+1] = (str[j+1] == 'r')?'g':'r';
					ary.push_back(clr_int(scp));
					break;
				}
			}
		}
		grh.push_back(ary);
	}
	return grh;
}

int main()
{
	string str;
	cin >> str;
	while(str.size() > 1)
	{
		auto graph = makeG(str.size());
		//cout << "l:" << str.size() << "r:" << graph.size() << endl;
		queue<pair<int,int>> q;
		q.push(pair<int,int>(clr_int(str),0));
		auto table = vector<int>(graph.size(),0);
		int c = 0;
		while(q.size() > 0)
		{
			auto n = q.front();
			if(graph[n.first].size() == 0)
			{
				cout << n.second << endl;
				break;
			}
			else if(c == graph.size())
			{
				cout << "NA" << endl;
				break;
			}
			else
			{
				const int l = graph[n.first].size();
				for(int i = 0;i < l;i++)
				{
					if(table[graph[n.first][i]] == 0)
					{
						table[graph[n.first][i]] = 1;
						c++;
						q.push(pair<int,int>(graph[n.first][i],n.second+1));
					}
				}
			}
			q.pop();
		}
		if(q.size() == 0)
		{
			cout << "NA" << endl;
		}
		cin >> str;
	}
	return 0;
}