#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
//#define int long long
using namespace std;

typedef pair<string, int> P;

string input;
set<string> checked;
queue<P> que;

bool check_all_same(string s)
{
	char color = s[0];
	for (int i=1; i<s.length(); i++)
	{
		if (color != s[i]) return false;
	}
	return true;
}

char get_other(char a, char b)
{
	//             r     g     b
	bool arr[3] = {true, true, true};
	if (a == 'r') arr[0] = false;
	if (a == 'g') arr[1] = false;
	if (a == 'b') arr[2] = false;
	if (b == 'r') arr[0] = false;
	if (b == 'g') arr[1] = false;
	if (b == 'b') arr[2] = false;
	rep(i,3)
	{
		if (arr[i])
		{
			if (i == 0) return 'r';
			else if (i == 1) return 'g';
			else return 'b';
		}
	}
}

vector<string> get_next_str(string in)
{
	vector<string> ret;

	for (int i=0; i<in.length()-1; i++)
	{
		if (in[i] != in[i + 1])
		{
			string next(in);
			char new_char = get_other(in[i], in[i + 1]);
			next[i] = new_char;
			next[i + 1] = new_char;

			ret.push_back(next);
		}
	}

	return ret;
}

signed main()
{
	/*
	vector<string> nexts = get_next_str("rbgrg");
	for (int i=0; i<nexts.size(); i++)
	{
		cout << nexts[i] << endl;
	}
	*/

	while (true)
	{
		cin >> input;
		if (input == "0") break;

		checked.clear();
		checked.insert(input);

		queue<P> empty;
		swap(que, empty);
		que.push(P(input, 0));

		bool find = false;

		while (que.size())
		{
			P p = que.front(); que.pop();
			if (check_all_same(p.first))
			{
				printf("%d\n", p.second);
				find = true;
				break;
			}

			vector<string> nexts = get_next_str(p.first);
			rep(i,nexts.size())
			{
				if (checked.find(nexts[i]) == checked.end())
				{
					que.push(P(nexts[i], p.second + 1));
					checked.insert(nexts[i]);
				}
			}
		}

		if (!find) printf("NA\n");
	}
}