#include <iostream>
#include <map>
#include <queue>
#include <string>

#define rep(i, n) for (int i = 0; i < n; i++)

using namespace std;

char get_color(char c1, char c2) {
    if ((c1 == 'r' && c2 == 'g') || (c1 == 'g' && c2 == 'r'))
        return 'b';
    else if ((c1 == 'g' && c2 == 'b') || (c1 == 'b' && c2 == 'g'))
        return 'r';
    else
        return 'g';
}

bool is_finish(string s) {
    rep(i, s.size()) if (s[0] != s[i]) return false;
    return true;
}

string s;
void solve() {
    queue<string> worm;
    map<string, int> dict;

    int ans = -1;
    worm.push(s);
    while (worm.size()) {
        string t = worm.front();
        int now = dict[t];
        worm.pop();
        if (is_finish(t)) {
            ans = now;
            break;
        }

        rep(i, t.size() - 1) {
            if (t[i] != t[i + 1]) {
                string next = t;
                next[i] = next[i + 1] = get_color(t[i], t[i + 1]);
                if (dict.count(next) == 0) {
                    // cout << t << " -> " << next << endl;
                    worm.push(next);
                    dict[next] = now + 1;
                }
            }
        }
    }
    if(ans == -1) cout << "NA" << endl;
    else cout << ans << endl;
}

int main() {
    while (cin >> s) {
        if (s == "0") break;
        solve();
    }
}