#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
typedef pair<int,int> Pii;
typedef pair<string, int> Psi;
typedef vector<int> Vi;
const int INF = (1<<25);
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int bfs(string worm) {
  queue<Psi> q;
  q.push(Psi(worm, 0));
  map<string, int> m;

  while(!q.empty()) {
    Psi p = q.front(); q.pop();
    if(m[p.fr]) continue;
    bool flag = false;
    string s = p.fr;
    for(int i=0; i<s.size()-1; i++) {
      if(s[i] != s[i+1]) {
	flag = true; 
	break;
      }
    }

    if(!flag) return p.sc;
    m[p.fr] = p.sc;
    for(int i=0; i<s.size()-1; i++) {
      if(s[i] != s[i+1]) {
	string next = s;
	char c;
	if(s[i] != 'r' && s[i+1] != 'r') {
	  c = 'r';
	}
	else if(s[i] != 'g' && s[i+1] != 'g') {
	  c = 'g';
	}
	else if(s[i] != 'b' && s[i+1] != 'b') {
	  c = 'b';
	}
	next[i] = next[i+1] = c;
	q.push(Psi(next, p.sc+1));
      }
    }
  }
  return -1;
}

int main() {
  string s;
  while(cin>> s && s != "0") {
    int ans = bfs(s);
    if(ans >= 0) cout<< ans<< endl;
    else cout<< "NA"<< endl;
  }
} 