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

typedef pair<string,int> P;

int main()
{
  string body;
  int check = 0;

  while(1){
    cin >> body;
    if(body == "0")return 0;

    map<string,int> used;

    queue<P> que;

    que.push(P(body,0));
    while(!que.empty()){
      P p = que.front();que.pop();
      string now = p.first;
      int co = p.second;
      int c = 1;
      for(int i = 0;i < body.size();i++){
        if(now[0] == now[i+1])c++;
      }
      if(c == body.size()){
        cout << co << endl;
        check = 1;
        break;
      }
      if(used[now] == 1)continue;
      used[now] = 1;

      for(int i = 0;i < body.size()-1;i++){
        string next = now;
        if(next[i] == next[i+1])continue;
        if((next[i] == 'r' && next[i+1] == 'b') || (next[i] == 'b' && next[i+1] == 'r')){
          next[i] = 'g';
          next[i+1] = 'g';
          que.push(P(next,co+1));
        }
        if((next[i] == 'r' && next[i+1] == 'g') || (next[i] == 'g' && next[i+1] == 'r')){
          next[i] = 'b';
          next[i+1] = 'b';
          que.push(P(next,co+1));
        }
        if((next[i] == 'g' && next[i+1] == 'b') || (next[i] == 'b' && next[i+1] == 'g')){
          next[i] = 'r';
          next[i+1] = 'r';
          que.push(P(next,co+1));
        }
      }
    }
    if(check == 0)cout << "NA" << endl;
    check = 0;
  }
}