#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<complex>
#include<cfloat>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define EPS (1e-10)
using namespace std;

typedef unsigned int uint;
typedef long long ll;

int encode(char *buff, int &len){
  int ret = 0;
  len = 0;
  while(true){
    if(*buff == 'r'){
      ret <<= 2;
      ret += 0;
    }else if(*buff == 'g'){
      ret <<= 2;
      ret += 1;
    }else if(*buff == 'b'){
      ret <<= 2;
      ret += 2;
    }else{
      return ret;
    }
    buff++;
    len++;
  }
  return ret;
}

void print(int now, int len){
  REP(i,len){
    int t = (now >> (2 * i)) & ((1<<2) - 1);
    if(t == 0) putchar('r');
    if(t == 1) putchar('g');
    if(t == 2) putchar('b');
  }
  puts("");
}

int main(){
  char buff[64];
  int change[1<<6];

  memset(change, -1, sizeof(change));
  REP(i,3) REP(j,3) REP(k,3)
    if(i != j && j != k && i != k)
      change[i | (j << 2)] = (k | (k << 2));

  while(fgets(buff,sizeof(buff),stdin), *buff != '0'){
    int len;
    int now = encode(buff,len);

    int ans[3];
    REP(i,3){
      int tmp = 0;
      REP(j,len){
	tmp <<= 2;
	tmp += i;
      }
      ans[i] = tmp;
    }

    

    set<int> s;
    queue<int> q;
    int n = 0;
    q.push(now);
    q.push(-1);
    s.insert(now);

    while(true){
      now = q.front();

      bool f = false;
      REP(i,3){
	if(ans[i] == now){
	  printf("%d\n",n);
	  f = true;
	  break;
	}
      }
      if(f) break;

      q.pop();
      
      if(q.empty()){
	puts("NA");
	break;
      }

      if(now == -1){
	n++;
	q.push(-1);
	continue;
      }

      //printf("now: "); print(now,len);

      REP(i,len-1){
	int cc   = (now >> (i * 2)) & ((1<<4) - 1);

	if(change[cc] != -1){
	  int next = now & ~(((1<<4)-1) << (i * 2));
	  next |= (change[cc] << (i * 2));
	  //print(next, len);
	  if(s.find(next) == s.end()){
	    s.insert(next);
	    q.push(next);
	  }
	}
      }
    }

  }
  return 0;
}