#include<iostream>
#include<queue>
#include<map>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < (n) ; ++i )
bool same(string s){
  rep(i,s.size()-1) if(s[i] != s[i+1]) return false;
  return true;
}
char change(char a,char b){
  if(a != 'b' && b != 'b') return 'b';
  if(a != 'g' && b != 'g') return 'g';
  return 'r';
}
int bfs(string s){
  queue<string>que;
  que.push(s);
  map<string,int> used;
  used[s] = 0;
  while(!que.empty()){
    string s = que.front(); que.pop();
    if(same(s)) return used[s];
    rep(i,s.size()-1){
      if(s[i] != s[i+1]){
        string next = s;
        next[i] = next[i+1] = change(next[i],next[i+1]);
        if(!used[next]) que.push(next) , used[next] = used[s] + 1;
      }
    }
  }
  return -1;
}
int main(){
  string s;
  while(cin >> s , s != "0"){
    int ans = bfs(s);
    if(ans == -1) cout << "NA" << endl;
    else cout << ans << endl;
  }
}