// 2011/02/23 Tazoe

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

struct change{
	string dat;
	int tim;
};

int main()
{
	while(true){
		struct change wor;
		cin >> wor.dat;
		if(wor.dat=="0")
			break;
		wor.tim = 0;

		queue<struct change> que;
		que.push(wor);

		map<string, bool> mem;

		int cost;
		while(true){
			if(que.empty()){
				cost = -1;
				break;
			}

			wor = que.front();
			que.pop();
//			cout << wor.dat << ' ' << wor.tim << endl;

			if(mem[wor.dat])
				continue;
			mem[wor.dat] = true;

			bool flg = true;
			for(int i=1; i<wor.dat.size(); i++)
				if(wor.dat[i]!=wor.dat[0]){
					flg = false;
					break;
				}
			if(flg){
				cost = wor.tim;
				break;
			}

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

		if(cost==-1)
			cout << "NA" << endl;
		else
			cout << cost << endl;
	}

	return 0;
}