#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <vector>
using namespace std;


int main()
{
	string first;
	queue<string> body;
	map<string, int> second;
	bool aligned = true;
	char changecolor;
	string tmp;

	while (1)
	{
		cin >> first;
		if (first[0] == '0') return 0;

		body.push(first);
		second[first] = 0;

		while (!body.empty())
		{
			aligned = true;

			for (int i = 0; i < body.front().size() - 1; ++i)
			{
				tmp = body.front();

				if (tmp[i] == 'r' && tmp[i + 1] == 'g') changecolor = 'b';
				if (tmp[i] == 'r' && tmp[i + 1] == 'b') changecolor = 'g';
				if (tmp[i] == 'g' && tmp[i + 1] == 'r') changecolor = 'b';
				if (tmp[i] == 'g' && tmp[i + 1] == 'b') changecolor = 'r';
				if (tmp[i] == 'b' && tmp[i + 1] == 'r') changecolor = 'g';
				if (tmp[i] == 'b' && tmp[i + 1] == 'g') changecolor = 'r';

				if (tmp[i] != tmp[i + 1])
				{
					aligned = false;
					tmp[i] = changecolor;
					tmp[i + 1] = changecolor;
				}

				if (second.count(tmp) == 0)
				{
					second[tmp] = second[body.front()] + 1;
					body.push(tmp);
				}
			}

			if (aligned)
			{
				cout << second[body.front()] << endl;
				break;
			}

			body.pop();
		}

		if(body.empty()) cout << "NA" << endl;

		first.clear();
		second.clear();
		while (!body.empty()) body.pop();
	}

	return 0;
}