#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <map>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<30;

char hage[] = {'r','g','b'};
char hoge(char a, char b) {
  REP(i,3)
    if (a != hage[i] && b != hage[i])
      return hage[i];
}
typedef pair<int, string> pis;

int bfs(string s) {
  int res = INF;
  queue<pis> Q;
  map<string, bool> ma;
  Q.push(pis(0,s));
  while(!Q.empty()) {
    pis p = Q.front(); Q.pop();
    string ss = p.second;
    if (ma[ss]) continue;
    ma[ss] = true;
//    cout << p.first << " " <<ss << endl;
    bool f = true;
    REP(i, ss.length()-1)
      if (ss[i] != ss[i+1])
        f = false;
    if (f) return p.first;
    REP(i, ss.length()-1) {
      if (ss[i] != ss[i+1]) {
        string sss = ss;
        sss[i] = sss[i+1] = hoge(ss[i], ss[i+1]);
        Q.push(pis(p.first + 1, sss));
      }
    }
  }
  return -1;
}

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