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

string insect = "brg";
int cnt;
queue <string> Q;
queue <string> Q2;

bool bfs( string str) {
  if ( cnt == 0 ) Q.push( str );
  while ( !Q2.empty() ) {
    string tmp;
    tmp = Q2.front();Q2.pop();
    Q.push(tmp);
  }
  
  int count = 0;
  while ( !Q.empty() ) {
    int flag = 0;
    count++;
    str = Q.front();
    Q.pop();
    string str2;
    int len = str.size();
    for ( int k = 0; k < len-1; k++ ) {
      if ( str[k] != str[k+1] ) flag = 1;
    }
    if ( flag == 0 ) return 1;
    for ( int i = 0; i < len-1; i++ ) {
      str2 = str;
      for ( int j = 0; j < 3; j++ ) {
	if ( str2[i] != str2[i+1] 
	     && str2[i] != insect[j] && str2[i+1] != insect[j] ) {
	  str2[i] = insect[j];
	  str2[i+1] = insect[j];
	  Q2.push( str2 );
	}
      }
    }
  }
  return 0;
}

int main() {

  while (1) {

    string str; cin >> str;
    if ( str == "0" ) break;
    while( !Q.empty() ) Q.pop();
    while( !Q2.empty() ) Q2.pop();
    cnt = -1;

    while (1) {
      cnt++;
      if ( cnt == 10 ){
	cout << "NA" << endl;
	break;
      }
      if ( bfs( str ) ) {
	cout << "ans" << " " << cnt << endl;
	break;
      }
    }

  }
  return 0;
}