#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<string, int> I;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
char rest(char a, char b){
  char rgb[5] = "rgb";
  REP(i,3){
    if(rgb[i] != a && rgb[i] != b){
      return rgb[i];
    }
  }
  return ',';
}
  
int bfs(I insect){
  set<string> memo;
  queue<I> que;
  que.push(insect);
  while(!que.empty()){
    I inc = que.front(); que.pop();
    string s = inc.first;
    int t = inc.second;

    if(memo.find(s) != memo.end()) continue;
    memo.insert(s);

    bool goal = true; 
    REP(i,s.size()-1){
      if(s[i] != s[i+1]){
        goal = false;
        string nxt = s;
        char rschar = rest(s[i],s[i+1]);
        if(rschar == '.') abort();
        nxt[i] = rschar;
        nxt[i+1] = rschar;
        que.push(I(nxt, t+1));
      }
    }
    if(goal) return t;
  }
  return -1;
}

int main(void){
  string insect;
  while(cin>>insect){
    if(insect == "0") break;
    int ans = bfs(I(insect, 0));
    if(ans == -1) cout<< "NA" << endl;
    else  cout<< ans << endl;
  }
  return 0;
}