#include <iostream>
#include <string>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, string> P;

string worm;

bool chkColor(int len){
  for(int i = 0; i < len - 1; ++i) if(worm[i] != worm[i + 1]) return false;
  return true;
}

int bfs(){

  int cnt, len = worm.length();
  queue<P> q; q.push(P(0, worm));
  map<string, bool> mpworm; mpworm[worm] = true;

  while(!q.empty()){

    P p = q.front(); q.pop();
    cnt = p.first;
    worm = p.second;

    if(chkColor(len)) return cnt;

    for(int i = 0; i < len - 1; ++i){

      char ncolor;
      string nworm = worm;

      if(worm[i] != worm[i + 1]){
        if(worm[i] == 'r' && worm[i + 1] == 'g' || worm[i] == 'g' && worm[i + 1] == 'r') ncolor = 'b';
  	    else if(worm[i] == 'g' && worm[i + 1] == 'b' || worm[i] == 'b' && worm[i + 1] == 'g') ncolor = 'r';
        else if(worm[i] == 'b' && worm[i + 1] == 'r' || worm[i] == 'r' && worm[i + 1] == 'b') ncolor = 'g';
        nworm[i] = ncolor;
        nworm[i + 1] = ncolor;
        if(mpworm[nworm] != true){
          mpworm[nworm] = true;
          q.push(P(cnt + 1, nworm));
        }
      }

    }

  }
  return -1;
}


int main(){

  int ans;

  while(1){

    cin >> worm;
    if(worm == "0")break;
    ans = bfs();
    if(ans == -1)cout << "NA" << endl;
    else cout << ans << endl;

  }

  return 0;
}