#include<iostream>
#include<queue>
#include<cstdio>
#include<map>
#include<string>
 
using namespace std;
 
typedef pair<string,int> P;
 
bool judge(string str)
{
  for(int i=1;i<str.size();i++)
    if(str[0]!=str[i])return false;
  return true;
}
 
char getch(char c1, char c2)
{
  if(c1=='r'&&c2=='b'||c1=='b'&&c2=='r')return 'g';
  if(c1=='r'&&c2=='g'||c1=='g'&&c2=='r')return 'b';
  if(c1=='b'&&c2=='g'||c1=='g'&&c2=='b')return 'r';
}
 
int bfs(string str)
{
  queue<P> q;
  map<string,int> mat;
  q.push(P(str,0));
  while(!q.empty()){
    P p = q.front(); q.pop();
    string s=p.first;
    int n=p.second+1;
    if(mat[s])continue;
    if(judge(s)){
      return n-1;
    }
    mat[s]=n;
    for(int i=0;i<s.size()-1;i++){
      if(s[i]!=s[i+1]){
        string t=s;
        char ch=getch(t[i],t[i+1]);
        t[i]=t[i+1]=ch;
        q.push(P(t,n));
      }
    }
  }
  return -1;
}
 
int main(void)
{
  string str;
  while(cin>>str&&str!="0"){
    int res;
    res = bfs(str);
    if(~res)printf("%d\n",res);
    else puts("NA");
  }
  return 0;
}