#include<iostream>
#include<deque>
#include<cmath>
using namespace std;

int s_i(string str){
  int ans = 0;
  int tmp = 1;
  for(int i=0;i<str.size();i++){
    if(str[i] == 'g')ans += tmp;
    else if(str[i] == 'b')ans += 2 * tmp;
    tmp *= 3;
  }
  return ans;
}
int main(){
  string worm,tmp;
  deque<string> open,open2;
  char first;
  int ans,max;
  bool flag;
  bool check[100000];

  while(1){
    cin >> worm;
    if(worm == "0")break;

    max = 1;
    for(int i=0;i<worm.size();i++)max *= 3;
    for(int i=0;i<max;i++)check[i] = false;

    open.clear();
    open2.clear();

    open.push_back(worm);
    check[s_i(worm)] = true;
    ans = 0;

    while(1){
      while(open.size()){
	worm = open[0];
	open.pop_front();
	
	flag = true;
	first = worm[0];
	for(int i=1;i<worm.size();i++){
	  if(worm[i]!=first){
	    flag = false;
	    break;
	  }
	}
	if(flag)break;
	
	for(int i=0;i<worm.size()-1;i++){
	  if(worm[i]!=worm[i+1]){
	    tmp = worm;
	    if(worm[i]!= 'r' && worm[i+1] != 'r')tmp[i] = tmp[i+1] = 'r';
	    else if(worm[i]!= 'g' && worm[i+1] != 'g')tmp[i] = tmp[i+1] = 'g';
	    else if(worm[i]!= 'b' && worm[i+1] != 'b')tmp[i] = tmp[i+1] = 'b';
	    if(!check[s_i(tmp)]){
	      check[s_i(tmp)] = true;
	      open2.push_back(tmp);
	    }
	  }
	}
      }
      if(flag)break;
      if(!open2.size())break;
      open = open2;
      open2.clear();
      ans++;
    }
    if(flag)cout << ans << endl;
    else cout << "NA" << endl;
  }
}