#include <iostream>
#include <algorithm>
using namespace std;


string rgb = "rgb";
int tab[300];
int n;

int encode(string s){
  int ret = 0;
  for(int i=0; i<n; i++){
    ret *= 3;
    ret += tab[s[i]];
  }
  return ret;
}

string decode(int c){
  string s = "";
  for(int i=0; i<n; i++){
    s = rgb[c%3] + s;
    c /= 3;
  }
  return s;
}


int main(){
  int q[100000];
  int memo[100000];
  tab['r'] = 0;
  tab['g'] = 1;
  tab['b'] = 2;
  
  for(;;){
    for(int i=0; i<100000; i++){
      memo[i] = -1;
    }
    string s;
    cin >> s;
    if(s[0]=='0') break;
    n = s.length();
    
    int ql = 0;
    int qr = 1;
    q[0] = encode(s);
    memo[encode(s)] = 0;
    
    int found = 0;
    while(qr-ql>0){
      int c = q[ql];
      string s = decode(c);
//      cout << s << endl;
      int ok = 1;
      for(int i=0; i<n-1; i++){
        if(s[i]!=s[i+1]){
          ok = 0;
          break;
        }
      }
      if(ok){
        found = 1;
        cout << memo[c] << endl;
        break;
      }
      
      for(int i=0; i<n-1; i++){
        if(s[i]!=s[i+1]){
          string ns = s;
          if('r'!=s[i] && 'r'!=s[i+1]){
            ns[i] = 'r';
            ns[i+1] = 'r';
          }
          if('g'!=s[i] && 'g'!=s[i+1]){
            ns[i] = 'g';
            ns[i+1] = 'g';
          }
          if('b'!=s[i] && 'b'!=s[i+1]){
            ns[i] = 'b';
            ns[i+1] = 'b';
          }
          int nc = encode(ns);
          if(memo[nc]==-1){
            memo[nc] = memo[c]+1;
            q[qr] = nc;
            qr++;
          }
        }
      }
      
      ql++;
      
    }
    if(found==0){
      cout << "NA" << endl;
    }
  }
	return 0;
}