#include <bits/stdc++.h>

using namespace std;

#define TEMP_T template<typename T>
TEMP_T void sort(T& v){ sort(v.begin(), v.end()); }
TEMP_T void revs(T& v){ reverse(v.begin(), v.end()); }
TEMP_T void uniq(T& v){ sort(v); v.erase(unique(v.begin(), v.end())); }
TEMP_T void show(T& v, char delim=' ', char end='\n'){ for(int i=0; i<v.size()-1; i++) cout << v[i] << delim; cout << v[v.size()-1] << end; }
TEMP_T T    cums(T& v){ T r; r.push_back(v[0]); for(int i=1; i<v.size(); i++) r.push_back(r[i-1] + v[i]); return r; }
TEMP_T void maxe(T& v, T m){ v = max(v, m); }
TEMP_T void mine(T& v, T m){ v = min(v, m); }

static inline int in(){ int x; scanf("%d", &x); return x; }

struct Solver {
  Solver(const string& init) : init(init) {}
  char getAnotherColor(char a, char b){
    if (a > b) swap(a, b);
    if (a == 'b'){
      if (b == 'g') return 'r';
      return 'g';
    }
    return 'b';
  }
  bool is_end(const string& s){
    for (int i = 1; i < s.size(); i++){
      if (s[0] != s[i]) return false;
    }
    return true;
  }

  int solve(){
    queue<string> Q;
    set<string> vis;
    int turn = 0;
    
    Q.push(init);
    vis.insert(init);
    while (!Q.empty()){
      queue<string> nQ;
      while (!Q.empty()){
        string state = Q.front();
        Q.pop();
        if (is_end(state)){
          return turn;
        }
        for (int i = 0; i < state.size() - 1; i++){
          if (state[i] != state[i + 1]){
            char another = getAnotherColor(state[i], state[i + 1]);
            string next_state = state;
            next_state[i + 1] = next_state[i] = another;
            if (vis.find(next_state) != vis.end()) continue;
            vis.insert(next_state);
            nQ.push(next_state);
          }
        }
      }
      turn++;
      swap(Q, nQ);
    }
    return -1;
  }
  string init;
};

int main()
{
  string s;
  while (cin >> s, s != "0"){
    Solver solver(s);
    int turn = solver.solve();
    if (turn == -1) puts("NA");
    else printf("%d\n", turn);
  }
  return 0;
}