#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

string s;

int judge(string j){
  rep(i, j.size()-1) if(j[i] != j[i+1]) return 0;
  return 1;
}

int main(){
  while(cin >> s){
    if(s[0] == '0') break;

    queue<pair<string,int> >q;
    map<string, int>m;
    q.push(MP(s, 0));
    m[s] = 1;

    while(!q.empty()){
      pair<string, int> p = q.front(); q.pop();

      if(judge(p.F)){
	printf("%d\n", p.S);
	goto e;
      }

      rep(i, s.size()-1){
	string n = p.F;
	if(n[i] == n[i+1]) continue;
	if(n[i] == 'r' && n[i+1] == 'g') n[i] = n[i+1] = 'b';
	else if(n[i] == 'r' && n[i+1] == 'b') n[i] = n[i+1] = 'g';
	else if(n[i] == 'g' && n[i+1] == 'r') n[i] = n[i+1] = 'b';
	else if(n[i] == 'g' && n[i+1] == 'b') n[i] = n[i+1] = 'r';
	else if(n[i] == 'b' && n[i+1] == 'g') n[i] = n[i+1] = 'r';
	else if(n[i] == 'b' && n[i+1] == 'r') n[i] = n[i+1] = 'g';

	if(m.find(n) != m.end()) continue;
	q.push(MP(n, p.S+1));
	m[n] = 1;
      }
    }
    puts("NA");
  e:;
  }
  return 0;
}