#include <iostream>
#include <string>
#include <queue>
#include <map>

using namespace std;
typedef pair<string, int> P;

void solve()
{
	string str;
	while(cin >> str)
	{
		if(str == "0")
		{
			break;
		}
		bool flag = true;
		for(int j = 0; j < str.size() - 1; ++j)
		{
			if(str[j] != str[j + 1])
			{
				flag = false;
				break;
			}
		}
		if(flag)
		{
			cout << 0 << endl;
			continue;
		}
		queue<P> Que;
		Que.push(make_pair(str, 0));
		queue<P> NextQue;
		map<string, int> Map;
		int step = 0;
		while(true)
		{
			if(step == str.size())
			{
				cout << "NA" << endl;
				break;
			}
			while(!Que.empty())
			{
				for(int i = 0; i < str.size() - 1; ++i)
				{
					string body = Que.front().first;
					if(body[i] == 'b' && body[i + 1] == 'g')
					{
						body[i] = body[i + 1] = 'r';
					}
					else if(body[i] == 'b' && body[i + 1] == 'r')
					{
						body[i] = body[i + 1] = 'g';
					}
					else if(body[i] == 'g' && body[i + 1] == 'b')
					{
						body[i] = body[i + 1] = 'r';
					}
					else if(body[i] == 'g' && body[i + 1] == 'r')
					{
						body[i] = body[i + 1] = 'b';
					}
					else if(body[i] == 'r' && body[i + 1] == 'b')
					{
						body[i] = body[i + 1] = 'g';
					}
					else if(body[i] == 'r' && body[i + 1] == 'g')
					{
						body[i] = body[i + 1] = 'b';
					}
					bool flag = true;
					for(int j = 0; j < str.size() - 1; ++j)
					{
						if(body[j] != body[j + 1])
						{
							flag = false;
							break;
						}
					}
					if(flag)
					{
						cout << Que.front().second + 1 << endl;
						goto NEXT;
					}
					if(!Map[body])
					{
						NextQue.push(make_pair(body, Que.front().second + 1));
					}
					Map[body]++;
				}
				Que.pop();
			}
			while(!NextQue.empty())
			{
				Que.push(NextQue.front());
				NextQue.pop();
			}
			++step;
		}
NEXT:
		;
	}
}

int main()
{
	solve();
	return(0);
}