#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};

char worm[12];
int ans;
bool flag;
void bfs(){
  string change;
  map<string,int> used;
  queue<string> que;
  queue<int> zikan;
  que.push(worm);
  zikan.push(0);
  while(!que.empty()){
    string str = que.front();
    ans = zikan.front();
    que.pop();
    zikan.pop();
    for(int i = 0;i < str.length()-1;i++){//変化した状態が題意を満たすかチェック
      if(str[i] !=str[i+1]){
	break;
      }
      if(i ==str.length()-2){
	flag = true;
	return;
      }
    }
    for(int i = 0;i <strlen(worm)-1;i++){
      if(str[i]=='r'&&str[i+1]!='r'){
	if(str[i+1]=='b'){
	  change = str;
	  change[i] ='g';
	  change[i+1]='g';
	  if(used[change]==1){
	    continue;
	  }
	  que.push(change);
	  zikan.push(ans+1);
	  used[change]=1;
	}else if(str[i+1]=='g'){
	  change = str;
	  change[i] ='b';
	  change[i+1]='b';
	  if(used[change]==1){
	    continue;
	  }
	  que.push(change);
	  zikan.push(ans+1);
	  used[change]=1;
	}
      }else if(str[i] =='b'&&str[i+1]!='b'){
	if(str[i+1]=='r'){
	  change = str;
	  change[i] ='g';
	  change[i+1]='g';
	  if(used[change]==1){
	    continue;
	  }
	  que.push(change);
	  zikan.push(ans+1);
	  used[change]=1;
	}else if(str[i+1]=='g'){
	  change = str;
	  change[i] ='r';
	  change[i+1]='r';
	  if(used[change]==1){
	    continue;
	  }
	  que.push(change);
	  zikan.push(ans+1);
	  used[change]=1;
	}
      }
      else if(str[i]=='g'&&str[i+1]!='g'){
	if(str[i+1]=='b'){
	  change = str;
	  change[i] ='r';
	  change[i+1]='r';
	  if(used[change]==1){
	    continue;
	  }
	  que.push(change);
	  zikan.push(ans+1);
	  used[change]=1;
	}else if(str[i+1]=='r'){
	  change = str;
	  change[i] ='b';
	  change[i+1]='b';
	  if(used[change]==1){
	    continue;
	  }
	  que.push(change);
	  zikan.push(ans+1);
	  used[change]=1;
	}
      }
    }
  }
}

int main()
{
  while(cin>>worm){
    ans = 0;
    if(worm[0]=='0')
      return 0;
    flag = false;
    bfs();
    if(flag)
      cout <<ans<<endl;
    else
      cout <<"NA"<<endl;
  }
  return 0;
}