#include "bits/stdc++.h"
using namespace std;

int main(){
  while(true){
    string s;
    cin>>s;
    if(s[0]=='0')break;
    string sr(s.size(),'r');
    string sg(s.size(),'g');
    string sb(s.size(),'b');
    map<string,int> mp;
    queue<string> q;
    q.push(s);
    mp[s]=0;
    int f=0;
    for(int i=0;i<1e3;i++){
      string x=q.front();
      q.pop();
      for(int j=0;j<s.size()-1;j++){
        string y=x;
        if(y[j]=='r'&&y[j+1]=='g'){
          y[j]='b';
          y[j+1]='b';
        }
        if(y[j]=='b'&&y[j+1]=='g'){
          y[j]='r';
          y[j+1]='r';
        }
        if(y[j]=='r'&&y[j+1]=='b'){
          y[j]='g';
          y[j+1]='g';
        }
        if(y[j]=='g'&&y[j+1]=='b'){
          y[j]='r';
          y[j+1]='r';
        }
        if(y[j]=='g'&&y[j+1]=='r'){
          y[j]='b';
          y[j+1]='b';
        }
        if(y[j]=='b'&&y[j+1]=='r'){
          y[j]='g';
          y[j+1]='g';
        }
        //cout<<mp[x]+1<<" "<<y<<endl;
        if(y==sr||y==sb||y==sg){
          cout<<mp[x]+1<<endl;
          f=1;
          break;
        }
        if(mp[y]==0){
          mp[y]=mp[x]+1;
          q.push(y);
        }
      }
      if(f)break;
    }
    if(!f)cout<<"NA"<<endl;
  }
}

