#include <iostream>
#include <string>
#include <map>
#include <queue>

using namespace std;


class Insect{
public:
  string body;
  int sec;
  Insect(string body, int sec): body(body), sec(sec) {}
};

bool isOneColor(string str) {
  char c = str[0];
  for(int i = 1; i < str.length(); i++) {
    if(str[i] != c) return false;
  }
  return true;
}

int main() {
  while(1) {
    string str;
    getline(cin, str);
    if(str == "0") break;

    map<string, bool> visited;
    queue<Insect> Q;
    Q.push(Insect(str, 0));
    visited[str] = true;

    int sec = -1;
    while(!Q.empty()) {
      Insect s = Q.front();
      Q.pop();
      
      if(isOneColor(s.body)) {
	sec = s.sec;
	break;
      }

      for(int i = 0; i+1 < s.body.length(); i++) {
	if(s.body[i] != s.body[i+1]) {
	  string temp = s.body;
	  if(s.body[i] != 'r' && s.body[i+1] != 'r')
	    temp[i] = temp[i+1] = 'r';
	  if(s.body[i] != 'g' && s.body[i+1] != 'g')
	    temp[i] = temp[i+1] = 'g';
	  if(s.body[i] != 'b' && s.body[i+1] != 'b')
	    temp[i] = temp[i+1] = 'b';

	  if(!visited[temp]) {
	    Q.push(Insect(temp, s.sec+1));
	    visited[temp] = true;
	  }
	}
      }
    }

    if(sec == -1) {
      cout << "NA" << endl;
    } else {
      cout << sec << endl;
    }
  }
  return 0;
}