#include <iostream>
#include <queue>
#include <map>
using namespace std;
typedef pair<string,int>P;
int bfs(string worm){
  queue<P>que;
  que.push(P(worm,0));
  map<string,int>d;
  while(!que.empty()){
    P p = que.front();
    que.pop();

    if(d[p.first])continue;
    string str = p.first;
    bool flag = false;
    for(int i = 0 ; i < str.size()-1 ; i++ ){
      if(str[i] != str[i+1] ){
	flag = true;
	break;
      }
    }
    if(!flag)return p.second;
    d[p.first] = p.second;
    for(int i = 0 ; i < str.size()-1 ; i++ ){
      if(str[i] != str[i+1]){
	char tmp;
	string next;
	if(str[i] != 'b' && str[i+1] != 'b'){
	  tmp = 'b'; 
	}else if(str[i] != 'g' && str[i+1] != 'g'){
	  tmp = 'g';
	}else {
	  tmp = 'r';
	}
	next = str;
	next[i] = next[i+1] = tmp;
	que.push(P(next,p.second + 1));
      }
    }
  }
  return -1;
}

int main(){
  string worm; 
  while(  cin >> worm ){
    if(worm[0] == '0' )break;  
    int ret = bfs(worm);
    if(ret >= 0)cout << ret << endl;
    else cout << "NA" << endl;
  }
  return 0;
}