#include<complex>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<map>
#include<sstream>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<deque>
#include<queue>
#include<climits>
#include<list>
#include<stack>
#include<ctime>
#define all(n) n.begin(),n.end()
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define F first
#define S second
#define Iter(c) __typeof__((c).begin())
#define foreach(i,c) for(Iter(c) i = (c).begin();i != (c).end();++i)
#define pb push_back
#define INF (1<<27)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef unsigned long long ull;
typedef long long ll;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

typedef pair<string,int> SI;

bool ok(string s)
{
  char c = s[0];
  for(int i=0;i<s.length();i++)
    if(c != s[i])
      return false;
  return true;
}

char getc(char c,char cc)
{
  map<char,bool> index;
  index['r'] = false,index['b'] = false,index['g'] = false;
  index[c] = true;
  index[cc] = true;
  foreach(i,index)
    if(!(*i).S)
      return (*i).F;

}

int solve(string s)
{

  queue<SI> que;
  que.push(SI(s,0));
  map<string,bool> used;
  while(!que.empty())
    {
      SI si = que.front(); que.pop();

      if(used[si.F])
	continue;

      used[si.F] = true;
 
      if(ok(si.F))
	{
	  return si.S;
	}

      if(si.S > 15)
	continue;

      rep(i,si.F.length()-1)
	{
	  if(si.F[i] == si.F[i+1])
	    continue;
	  string news = si.F;
	  news[i] = news[i+1] = getc(si.F[i],si.F[i+1]);
	  que.push(SI(news,si.S+1));
	}

    }

  return -1;
}


int main(){

  while(true)
    {
      string s;
      cin >> s;
      if(s[0] == '0')
	break;

      int ans = solve(s);
      ans != -1?cout << ans << endl:cout << "NA" << endl;

    }

return 0;
}