#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main(){
  string worm;
  int cost[60000];
  int count = 0;
  while(1) {
    if(count > 60000) break;
    count++;
    cin >> worm;
    if(worm[0] == '0') break;

    int ima[10];
    for(int i=0;i<worm.size();i++) {
      if(worm[i] == 'r') ima[i] = 0;
      else if(worm[i] =='b') ima[i] = 1;
      else ima[i] = 2;
    }

    int t = 1,m = worm.size();
    int deci = 0;
    // 3 to 10
    for(int i=0;i<m;i++) {
      deci += ima[m-1-i]*t;
      t *= 3;
    }

   
    for(int i=0;i<60000;i++) cost[i] = 1000000000;  
    cost[deci] = 0;

    queue <int> Q;
    Q.push(deci);

    int befo[2];
    int a;
    int ans = 1000000000;
    while(!Q.empty()) {
      a = Q.front();
      Q.pop();
      int b = a;
      //      cout << a << endl;
      for(int i =0;i<m;i++) {
	ima[m-1-i] = b%3;
	b/=3;
      }
      
      //      cout << "start";
      //for(int i=0;i<m;i++) cout << ima[i];
      //cout << endl;
    
      for(int j=0;j<m-1;j++) {
	if(ima[j] != ima[j+1]) break;
	if(j == m-2) ans = min(ans,cost[a]);
      }
      

      int flg[3] = {};
      for(int i=0;i<m-1;i++) {
	if(ima[i] != ima[i+1]) {
	  befo[0] = ima[i];
	  befo[1] = ima[i+1];
	  flg[ima[i]] = flg[ima[i+1]] = 1;
	  for(int j=0;j<3;j++) if(flg[j] == 0) ima[i] = ima[i+1] = j;
	  // for(int j=0;j<m;j++) cout << ima[j];
	  // cout << endl;
	  t = 1;
	  deci = 0;
	  // 3 to 10
	  for(int j=0;j<m;j++) {
	    deci += ima[m-1-j]*t;
	    t *= 3;
	  }

	  if(cost[deci]  > cost[a]+1 && ans > cost[a] +1 ) {
	    cost[deci] = cost[a]+1;
	    // cout << "deci ="<< deci << endl;
	    Q.push(deci);
	  }
	  ima[i] = befo[0];
	  ima[i+1] = befo[1];
	  flg[0] = flg[1] = flg[2] = 0;
	}
      }
    }
	



    if(ans == 1000000000) cout <<"NA" <<endl;
    else cout << ans << endl;


  }	
	return 0;
}