#include <bits/stdc++.h>
using namespace std;

bool isOneColor(const string &s) {
  for(int i = 1; i < s.size(); ++i)
    if(s[0] != s[i]) return false;
  return true;
}

int bfs(string src) {
  if(isOneColor(src)) return 0;
  const static string color = "rgb";
  map<string,int> cost;
  queue<string> que;
  cost[src] = 0;
  que.push(src);
  while(que.size()) {
    const string s = que.front();
    que.pop();
    for(int i = 0; i+1 < s.size(); ++i) {
      if(s[i] == s[i+1]) continue;
      string t = s;
      for(int j = 0; j < color.size(); ++j) {
        if(t[i] != color[j] && t[i+1] != color[j]) {
          t[i] = t[i+1] = color[j];
          break;
        }
      }
      if(cost.count(t)) continue;
      cost[t] = cost[s] + 1;
      que.push(t);
      if(isOneColor(t)) return cost[t];
    }
  }
  return -1;
}

int main() {
  string s;
  while(cin >> s && s != "0") {
    int res = bfs(s);
    if(res == -1) cout << "NA" << endl;
    else cout << res << endl;
  }
  return 0;
}