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

using namespace std;

const int inf = 99999;

struct St{
  string worm;
  int cnt;
};

typedef map<string, bool> Mp;

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;
}

char getC(char s, char t)
{
  if((s == 'r' && t == 'g') || (s == 'g' && t == 'r')){
    return 'b';
  }
  if((s == 'r' && t == 'b') || (s == 'b' && t == 'r')){
    return 'g';
  }

  return 'r';
}

int bfs(string str)
{
  int r = inf+1;
  queue<St> que;
  map<string, bool> mpp;
  St st1, st2;
  st1.worm = str;
  st1.cnt = 0;
  que.push(st1);
  mpp[str] = true;

  while(!que.empty()){
    st1 = que.front();
    que.pop();
    if(check(st1.worm) || st1.cnt > inf){
      r = st1.cnt;
      break;
    }

    for(int i = 0; i < (st1.worm).size()-1; i++){
      string s1 = st1.worm;
      if(s1[i] != s1[i+1]){
	s1[i] = s1[i+1] = getC(s1[i], s1[i+1]);
	if(!mpp[s1]){
	  mpp[s1] = true;
	  st2.worm = s1;
	  st2.cnt = st1.cnt+1;
	  que.push(st2);
	}
      }
    }
  }


  return r;
}

int main()
{
  int t;
  string str;

  while(cin>>str && str != "0"){
    t = bfs(str);
    if(t > inf){
      cout << "NA" << endl;
    } else {
      cout << t << endl;
    }
  }

  return 0;
}