#include <iostream>
#include <queue>
#include <map>
#include <cstring>
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 = true;
    for(int i = 0; i < str.size()-1; i++){
      if(str[i] != str[i+1]){
        flag = false;
        break;
      }
    }

    if(flag) return p.second;

    for(int i = 0; i < str.size()-1; i++){
      if(str[i] != str[i+1]){
        string next;
        char tmp;
        if(str[i] != 'r' && str[i+1] != 'r'){
          tmp = 'r';
        }else if(str[i] != 'b' && str[i+1] != 'r'){
          tmp = 'b';
        }else{
          tmp = 'g';
        }

        next = str;
        next[i] = next[i+1] = tmp;
        que.push(P(next, p.second+1));
      }
    }
  }
  return -1;
}

int main(void){
  string worm;
  while(cin >> worm && worm != "0"){
    int ans = bfs(worm);
    if(ans >= 0)  cout << ans << endl;
    else cout << "NA" << endl;
  }

  return 0;
}