#include <bits/stdc++.h>
using namespace std;
using P = pair<string, int>;

int main() {
  map<char, int> rbg;
  rbg['r'] = 0;
  rbg['b'] = 1;
  rbg['g'] = 2;

  string s;
  while (cin >> s && s[0] != '0') {
    int len = s.length();
    vector<string> goal(3);
    for (int i = 0; i < 3; ++i) {
      goal[i] = string(len, "rbg"[i]);
    }

    auto check = [&](string s) {
      for (int i = 0; i < 3; ++i) {
        if (goal[i] == s) return true;
      }
      return false;
    };
    int ans;
    bool ok = true;
    queue<P, deque<P>> que;
    map<string, bool> mp = {{s, true}};

    que.push({s, 0});
    while (ok) {
      tie(s, ans) = que.front(); que.pop();
      if (check(s)) break;

      for (int i = 0; i < len - 1; ++i) {
        if (s[i] == s[i + 1]) continue;
        string nxt = s;
        int n = 3 - rbg[s[i]] - rbg[s[i + 1]];
        nxt[i] = nxt[i + 1] = "rbg"[n];
        if (!mp[nxt]) {
          que.push({nxt, ans + 1});
          mp[nxt] = true;
        }
      }
      if (que.empty()) ok = false;
    }
    cout << ( (ok) ? to_string(ans) : "NA" ) << endl;
  }
  return 0;
}

