#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,string> P;
int main(){
  string s1;
  int i;
  while(1){
    cin >> s1;
    if(s1=="0"){
      return 0;
    }
    int ans=(1<<29);
    map<string,int> mp;
    queue<P> que;
    que.push(P(0,s1));
    while(!que.empty()){
      int x=que.front().first;
      string s=que.front().second;
      que.pop();
      if(mp.find(s)!=mp.end() && mp[s]<=x){
        continue;
      }
      if(x>=ans){
        continue;
      }
      mp[s]=x;
      int res=0;
      for(i=1;i<s.size();i++){
        if(s[i-1]!=s[i]){
          res=1;
          break;
        }
      }
      if(res==0){
        ans=x;
        continue;
      }
      for(i=1;i<s.size();i++){
        string t=s;
        if(s[i-1]=='r' && s[i]=='g'){
          t[i-1]='b',t[i]='b';
          que.push(P(x+1,t));
        }
        if(s[i-1]=='r' && s[i]=='b'){
          t[i-1]='g',t[i]='g';
          que.push(P(x+1,t));
        }
        if(s[i-1]=='g' && s[i]=='b'){
          t[i-1]='r',t[i]='r';
          que.push(P(x+1,t));
        }
        if(s[i-1]=='g' && s[i]=='r'){
          t[i-1]='b',t[i]='b';
          que.push(P(x+1,t));
        }
        if(s[i-1]=='b' && s[i]=='g'){
          t[i-1]='r',t[i]='r';
          que.push(P(x+1,t));
        }
        if(s[i-1]=='b' && s[i]=='r'){
          t[i-1]='g',t[i]='g';
          que.push(P(x+1,t));
        }
      }
    }
    if(ans==(1<<29)){
      cout << "NA" << endl;
      continue;
    }
    cout << ans << endl;
  }
}
