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

map<char, char> rot = {
    {'r', 'g'}, {'g', 'b'}, {'b', 'r'}
};
map<string, bool> used;

void rotate(string &s) {
    for (int i=0; i<(int)s.size(); ++i) s[i] = rot[s[i]];
}

int main() {
    string s;
    while (cin >> s, s != "0") {
        used.clear();
        string r = "", g = "", b = "";
        for (int i=0; i<(int)s.size(); ++i) {
            r += "r"; g += "g"; b += "b";
        }
        queue<pair<string,int> > q;
        q.push(make_pair(s, 0));
        int res = -1;
        while ( ! q.empty()) {
            string col = q.front().first;
            used[col] = true; rotate(col);
            used[col] = true; rotate(col);
            used[col] = true; rotate(col);
            int t = q.front().second;
            if (col == r || col == g || col == b) {
                res = t;
                break;
            }
            q.pop();
            for (int i=0; i<(int)col.size()-1; ++i) {
                if (col[i] != col[i+1]) {
                    string nxt = col;
                    if (col[i] != 'r' && col[i+1] != 'r') {
                        nxt[i] = 'r'; nxt[i+1] = 'r';
                    } else if (col[i] != 'g' && col[i+1] != 'g') {
                        nxt[i] = 'g'; nxt[i+1] = 'g';
                    } else if (col[i] != 'b' && col[i+1] != 'b') {
                        nxt[i] = 'b'; nxt[i+1] = 'b';
                    }
                    if ( ! used[nxt]) {
                        q.push(make_pair(nxt, t+1));
                    }
                }
            }
        }
        if (res < 0) {
            cout << "NA" << endl;
        } else {
            cout << res << endl;
        }
    }
    return 0;
}