#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

bool check(string s) {
  for (int i = 0; i < int(s.size()); i++) {
    if (s[i] != s[0]) return false;
  }
  return true;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  const string col = "rgb";
  string s;
  while (cin >> s, s != "0") {
    int n = s.size();
    map<string, int> dis;
    queue<string> que;
    dis[s] = 0;
    que.emplace(s);
    int ans = -1;
    while (!que.empty()) {
      s = que.front(); que.pop();
      if (check(s)) {
        ans = dis[s];
        break;
      }
      for (int i = 0; i + 1 < n; i++) {
        if (s[i] == s[i + 1]) continue;
        for (int j = 0; j < 3; j++) {
          if (s[i] != col[j] && s[i + 1] != col[j]) {
            string ns = s;
            ns[i] = ns[i + 1] = col[j];
            if (dis.find(ns) != dis.end()) continue;
            dis[ns] = dis[s] + 1;
            que.emplace(ns);
          }
        }
      }
    }
    if (ans < 0) cout << "NA" << endl;
    else cout << ans << endl;
  }

  return 0;
}
