#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

typedef pair<string,int> P;

string change(char a, char b) {
  string s;
  if((a=='r' && b=='g') || (a=='g' && b=='r')) s="bb";
  if((a=='r' && b=='b') || (a=='b' && b=='r')) s="gg";
  if((a=='g' && b=='b') || (a=='b' && b=='g')) s="rr";
  return s;
}

int main() {
  string t;
  while(cin >> t && t!="0") {
    map<string,int> color;
    queue<P> que;
    que.push(P(t,0));
    color[t]=1;
    int ans=-1;
    while(!que.empty()) {
      P p=que.front();
      que.pop();
      string s=p.first;
      bool ck=true;
      for(int i=0; i<s.size()-1; i++) {
	if(s[i]!=s[i+1]) {
	  string r;
	  r=s.substr(0,i)+change(s[i],s[i+1])+s.substr(i+2,s.size()-i-2);
	  if(color[r]!=1) {
	    que.push(P(r,p.second+1));
	    color[r]=1;
	  }
	  ck=false;
	}
      }
      if(ck) {
	ans=p.second;
	break;
      }
    }
    if(ans==-1) cout << "NA" << endl;
    else cout << ans << endl;
  }
  return 0;
}
