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

using namespace std;

void solve()
{
	string str;
	while(cin >> str)
	{
		if(str == "0")
		{
			break;
		}
		queue<string> Que;
		Que.push(str);
		queue<string> NextQue;
		int depth = 0;
		while(true)
		{
			if(depth >= 10)
			{
				cout << "NA" << endl;
				break;
			}
			while(!Que.empty())
			{
				string worm = Que.front();
				Que.pop();
				bool same_color_flag = true;
				for(int i = 1; i < worm.size(); ++i)
				{
					if(worm[i] != worm[0])
					{
						same_color_flag = false;
					}
				}
				if(same_color_flag)
				{
					cout << depth << endl;
					goto END;
				}
				char before_color = worm[0];
				for(int i = 1; i < worm.size(); ++i)
				{
					if(before_color != worm[i])
					{
						string next = worm;
						if(before_color == 'b')
						{
							if(worm[i] == 'g')
							{
								next[i - 1] = 'r';
								next[i] = 'r';
							}
							else if(worm[i] == 'r')
							{
								next[i - 1] = 'g';
								next[i] = 'g';
							}
						}
						else if(before_color == 'g')
						{
							if(worm[i] == 'b')
							{
								next[i - 1] = 'r';
								next[i] = 'r';
							}
							else if(worm[i] == 'r')
							{
								next[i - 1] = 'b';
								next[i] = 'b';
							}
						}
						else if(before_color == 'r')
						{
							if(worm[i] == 'g')
							{
								next[i - 1] = 'b';
								next[i] = 'b';
							}
							else if(worm[i] == 'b')
							{
								next[i - 1] = 'g';
								next[i] = 'g';
							}
						}
						NextQue.push(next);
					}
					before_color = worm[i];
				}
			}
			while(!NextQue.empty())
			{
				Que.push(NextQue.front());
				NextQue.pop();
			}
			++depth;
		}
END:
		;
	}
}

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