#include <iostream>
#include <set>
#include <queue>

struct Worm {
	std::string body;
	int step;
	Worm() {}
	Worm(std::string body, int step) : body(body), step(step) {}
};

bool meetColor(std::string body)
{
	char c = body[0];
	for (int i=1; i<body.length(); i++) {
		if (body[i] != c) return false;
	}
	return true;
}

int getMinStep(std::queue<Worm> que, std::set<std::string>& checked)
{
	while (!que.empty()) {
		Worm worm = que.front(); que.pop();
		if (meetColor(worm.body)) return worm.step;
		if (checked.find(worm.body) != checked.end()) continue;
		checked.insert(worm.body);
		for (int i=0; i<worm.body.length()-1; i++) {
			if (worm.body[i] == worm.body[i+1]) continue;
			std::string new_body = worm.body;
			if (new_body[i] == 'r' && new_body[i+1] == 'g') new_body[i] = new_body[i+1] = 'b';
			else if (new_body[i] == 'r' && new_body[i+1] == 'b') new_body[i] = new_body[i+1] = 'g';
			else if (new_body[i] == 'g' && new_body[i+1] == 'r') new_body[i] = new_body[i+1] = 'b';
			else if (new_body[i] == 'g' && new_body[i+1] == 'b') new_body[i] = new_body[i+1] = 'r';
			else if (new_body[i] == 'b' && new_body[i+1] == 'r') new_body[i] = new_body[i+1] = 'g';
			else new_body[i] = new_body[i+1] = 'r';
			que.push(Worm(new_body, worm.step+1));
		}
	}
	return -1;
}

int main()
{
	std::string worm;
	while (true) {
		std::cin >> worm;
		if (worm=="0") break;
		std::queue<Worm> que;
		que.push(Worm(worm,0));
		std::set<std::string> checked;
		int res = getMinStep(que, checked);
		if (res >= 0) std::cout << res << std::endl;
		else std::cout << "NA" << std::endl;
	}
	return 0;
}

