#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
typedef pair<string,int> Psi;

string in;

inline bool check(const string& str) {
  rep (i,str.size()) if (str[0] != str[i]) return false;
  return true;
}

char another(const char a, const char b) {
  static const char cs[3] = { 'r', 'g', 'b' };
  rep (i,3) if (cs[i] != a && cs[i] != b) return cs[i];
}

int main() {
  while (cin >> in) {
    if (in == "0") break;
    if (check(in)) { cout << 0 << endl; continue; }
    
    queue<Psi> q;
    set<string> s;
    q.push(make_pair(in, 0));

    int ans = -1;
    while (!q.empty()) {
      Psi p = q.front(); q.pop();
      string str = p.first;
      
      if (s.count(str)) continue;
      s.insert(str);
      
      if (check(str)) {
        ans = p.second;
        break;
      }
      
      for (int i = 0; i < str.size() - 1; ++i) {
        if (str[i] != str[i+1]) {
          string copy = str;
          char c = another(str[i], str[i+1]);
          copy[i] = copy[i+1] = c;
          q.push(make_pair(copy, p.second + 1));
        }
      }
    }
    
    
    if (ans == -1) {
      cout << "NA" <<endl;
    } else {
      cout << ans << endl;
    }
  }
  return 0;
}