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

typedef pair<string, int> psi;

int bfs(string worm) {
  queue<psi> que;
  que.push(psi(worm, 0));

  map<string, int> d;

  while (!que.empty()) {
    psi p = que.front();
    que.pop();

    if (d[p.first]) continue;

    string str = p.first;

    bool flag = false;
    for (int i = 0; i < str.size() - 1; i++) {
      if (str[i] != str[i+1]) {
	  flag = true;
	  break;
      }
    }

    if (!flag) return p.second;

    d[p.first] = p.second;

    for (int i = 0; i < str.size() - 1; i++) {
      if (str[i] != str[i+1]) {
	char temp;
	string next;

	if (str[i] != 'b' && str[i+1] != 'b') {
	  temp = 'b';
	} else if (str[i] != 'g' && str[i+1] != 'g') {
	  temp = 'g';
	} else {
	  temp = 'r';
	}

	next = str;
	next[i] = next[i+1] = temp;

	que.push(psi(next, p.second+1));
      }
    }
  }
  return -1;
}

int main(void) {
  string worm;
  while (cin >> worm) {
    if (worm[0] == '0') {
      break;
    }

    int ret = bfs(worm);
    if (ret != -1) {
      cout << ret << endl;
    } else {
      cout << "NA" << endl;
    }
  }

  return 0;
}