#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
typedef long long int lli;
using namespace std;

int main(){
	string str;
	while(cin>>str&&str!="0"){
		map<string,int> d;
		queue<string> que;
		que.push(str);
		d[str]=0;
		int flag1=true;
		while(que.size()){
			string tmp=que.front();
			que.pop();
			int flag2=true;
			char a=tmp[0];
			for(int i=1; i<tmp.size(); ++i){
				if(a!=tmp[i]) {
					flag2=false;
					break;
				}
				a=tmp[i];
			}
			if(flag2){
				cout << d[tmp] << "\n";
				flag1=false;
				break;
			}
			for(int i=0; i+1<tmp.size(); ++i){
				if(tmp[i]!=tmp[i+1]){
					string nstr=tmp;
					if(tmp[i]!='r'&&tmp[i+1]!='r'){
						nstr[i]='r';
						nstr[i+1]='r';
					} else if(tmp[i]!='g'&&tmp[i+1]!='g'){
						nstr[i]='g';
						nstr[i+1]='g';
					} else if(tmp[i]!='b'&&tmp[i+1]!='b'){
						nstr[i]='b';
						nstr[i+1]='b';
					}
					if(nstr[i]==nstr[i+1]&&d.count(nstr)==0){
						que.push(nstr);
						d[nstr]=d[tmp]+1;
					}
				}
			}
		}
		if(flag1) cout << "NA\n";
	}
	return 0;
}