#include <iostream>
#include <queue>
#include <map>
#define INF 10000000
using namespace std;
typedef pair<string ,int>P;
int cnt;

int bfs(string worm){
  map<string,int>used;
  queue<P> que;
  que.push(P(worm,0));
  string next;
  
  while(!que.empty()){
    char tmp;
    P p = que.front();
    que.pop();
    if(used[p.first] == 1)continue;
    bool f = true;
    string str = p.first;
    for(int i = 0 ; i < p.first.size()-1 ; i++ ){
      if(str[i] != str[i+1])f = false;
    }
    if(f)return p.second;
    used[p.first] = 1;
    for(int i = 0 ; i < worm.size()-1 ; i++ ){
      if(str[i] != str[i+1]){
	if(str[i] != 'r' && str[i+1] != 'r'){
	  tmp = 'r';
	}else if(str[i] != 'g' && str[i+1] != 'g'){
	  tmp = 'g';
	} else {
	  tmp = 'b';
      }
	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;
    cnt = 0;
    int ret = bfs(worm);
    if(ret == -1){
      cout << "NA" << endl;
    }else cout << ret << endl;
    
  }
  return 0;
}