#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') {
    vector<string> goal;
    for (int i = 0; i < 3; ++i) goal.push_back(string(s.length(), "rbg"[i]));

    auto check = [&](string s) {
      for (int i = 0; i < 3; ++i) {
        if (goal[i] == s) return true;
      }
      return false;
    };

    map<string, bool> mp; mp[s] = true;
    queue<P, deque<P>> que; que.push({s, 1});

    int ans = 0;
    bool ok = check(s);
    while (!que.empty() && !ok) {
      tie(s, ans) = que.front(); que.pop();
      if (!mp[s]) continue;

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

