// 2011/08/21 Tazoe

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

struct state{
	string seg;
	int tim;
};

int main()
{
	while(true){
		struct state wrm;
		cin >> wrm.seg;
		if(wrm.seg=="0")
			break;
		wrm.tim = 0;

		queue<struct state> que;
		que.push(wrm);

		map<string, bool> memo;

		while(true){
			if(que.empty()){
				cout << "NA" << endl;
				break;
			}

			wrm = que.front();
			que.pop();

			if(memo[wrm.seg])
				continue;
			else
				memo[wrm.seg] = true;

			bool flg = true;
			for(int i=1; i<wrm.seg.size(); i++)
				if(wrm.seg[i]!=wrm.seg[0]){
					flg = false;
					break;
				}
			if(flg){
				cout << wrm.tim << endl;
				break;
			}

			struct state tmp;
			for(int i=0; i<wrm.seg.size()-1; i++)
				if(wrm.seg[i]==wrm.seg[i+1])
					continue;
				else if(wrm.seg[i]!='r'&&wrm.seg[i+1]!='r'){
					tmp.seg = wrm.seg;
					tmp.seg[i] = tmp.seg[i+1] = 'r';
					tmp.tim = wrm.tim+1;
					que.push(tmp);
				}
				else if(wrm.seg[i]!='g'&&wrm.seg[i+1]!='g'){
					tmp.seg = wrm.seg;
					tmp.seg[i] = tmp.seg[i+1] = 'g';
					tmp.tim = wrm.tim+1;
					que.push(tmp);
				}
				else if(wrm.seg[i]!='b'&&wrm.seg[i+1]!='b'){
					tmp.seg = wrm.seg;
					tmp.seg[i] = tmp.seg[i+1] = 'b';
					tmp.tim = wrm.tim+1;
					que.push(tmp);
				}
		}
	}

	return 0;
}