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

using namespace std;

int ans;
const int MAX_COUNT = 1000;
char color[3] = {'r', 'g', 'b'};
set<string> mSet;

typedef pair<string, int> PSI;

bool solve(string str)
{
	queue<PSI> que;
	que.push(PSI(str, 0));
	
	while(!que.empty())
	{
		PSI current = que.front();
		que.pop();

		bool is_solved = true;
		for(int i=0; i<current.first.size()-1; i++)
		{
			if(current.first[i] != current.first[i+1])
			{
				is_solved = false;
				break;
			}
		}

		if(is_solved)
		{
			ans = current.second;
			return true;
		}

		if(mSet.find(current.first) == mSet.end())
		{
			mSet.insert(current.first);
		}
		else
		{
			continue;
		}

 		for(int i=0; i<current.first.size()-1; i++)
		{
			if(current.first[i] != current.first[i+1])
			{
				for(int k=0; k<3; k++)
		   		{
	   				if(current.first[i] != color[k] && current.first[i+1] != color[k])
   					{
				   		string new_str = string(current.first.begin(), current.first.end());
			   			new_str[i] = color[k];
		  				new_str[i+1] = color[k];
						que.push(PSI(new_str, current.second+1));
					}
				}
			}
		}
	}

	return false;
}

int main()
{
	string str;
	while( 1 )
	{
		cin >> str;
		if(str == "0") break;

		ans = MAX_COUNT;
		mSet.clear();

		if(!solve(str))
		{
			printf("NA\n");
		}
		else
		{
			printf("%d\n", ans);
		}
	}
}