#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct St{
  string worm;
  int cnt;
};

bool check(string str)
{
  bool f = true;  

  for(int i = 1; i < str.size(); i++){
    if(str[i] != str[0]){
      f = false;
      break;
    }
  }

  return f;
}

int bfs(string str)
{
  int r = 101;
  vector<St> vec;
  St stt, stt2;
  stt.worm = str;
  stt.cnt = 0;

  vec.push_back(stt);
  while(!vec.empty()){
    stt = vec[0];
    vec.erase(vec.begin());

    if(check(stt.worm) || stt.cnt > 10){
      r = stt.cnt;
      break;
    }

    for(int i = 0; i < (stt.worm).size()-1; i++){
      string s = stt.worm;
      if(s[i] != s[i+1]){
	if((s[i] == 'r' && s[i+1] == 'g')||(s[i] == 'g' && s[i+1] == 'r')){
	  s[i] = s[i+1] = 'b';
	} else if((s[i] == 'r' && s[i+1] == 'b')||(s[i] == 'b' && s[i+1] == 'r')){
	  s[i] = s[i+1] = 'g';
	} else {
	  s[i] = s[i+1] = 'r';
	}

	bool f = true;
	for(int j = 0; j < vec.size(); j++){

	  if(vec[j].worm == s){
	    f = false;
	    break;
	  }
	}

	if(f){
	  stt2.worm = s;
	  stt2.cnt = stt.cnt + 1;
	  vec.push_back(stt2);
	}
      }
    }

  }

  return r;
}

int main()
{
  int t;
  string str;

  while(cin>>str && str != "0"){

    t = bfs(str);
    if(t > 10){
      cout << "NA" << endl;
    } else {
      cout << t << endl;
    }
  }

  return 0;
}