// AOJ 0179
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<functional>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

typedef long long int integer;

bool end(string s) {
  char c = s[0];
  int len = s.size();
  REP(i, len) {
    if (c != s[i]) {
      return false;
    }
  }
  return true;
}

vector<string> gonext(string worm) {
  vector<string> v;
  for (int i = 1, len = worm.length(); i < len; i++) {
    if (worm[i] == worm[i-1]) continue;
    string s = worm;
    char c = 'r' + 'g' + 'b' - worm[i] - worm[i-1];
    s[i] = s[i-1] = c;
    v.push_back(s);
  }
  return v;
}

typedef pair<integer,string> P;

integer solve(string worm) {
  priority_queue<P,vector<P>,greater<P> > q;
  set<string> s;
  q.push(make_pair(0,worm));
  while (!q.empty()) {
    P w = q.top();
    q.pop();
    if (end(w.second)) return w.first;
    vector<string> nxts = gonext(w.second);
    for (auto nxt : nxts) {
      if (s.find(nxt) == s.end()) {
        q.push(make_pair(w.first + 1, nxt));
        s.insert(nxt);
      }
    }
  }
  return -1;
}

int main() {
  string s;
  while (cin >> s and s != "0") {
    integer ans = solve(s);
    if (ans == -1) {
      cout << "NA" << endl;
    } else {
      cout << ans << endl;
    }
  }
}