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

char rgb(char a, char b) {
    assert(a != b);
    if (a == 'r') {
        if (b == 'g') return 'b';
        else if (b == 'b') return 'g';
    } else if (a == 'g') {
        if (b == 'r') return 'b';
        else if (b = 'b') return 'r';
    } else {
        if (b == 'r') return 'g';
        else if (b == 'g') return 'r';
    }
    exit(1);
}

struct state_t {
    string worm;
    int count;
    state_t(string worm, int count) : worm(worm), count(count) {}
};

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

int main() {
    string s;
    while (getline(cin, s)) {
        if (s == "0") break;

        queue<state_t> q;
        set<string> cache;

        q.push(state_t(s, 0));

        bool found = false;
        while (!q.empty()) {
            state_t p = q.front(); q.pop();
            string u = p.worm;
//            cout << u << endl;
            if (cache.count(u)) continue;
            cache.insert(u);
            if (same_characters(u)) {
                cout << p.count << endl;
                found = true;
                break;
            }
            for (int i = 0; i < u.size()-1; i++) {
                if (!(u[i] == u[i+1])) {
                    char c = rgb(u[i], u[i+1]);
                    string t = u; t[i] = t[i+1] = c;
                    q.push(state_t(t, p.count+1));
                }
            }
        }

        if (!found) cout << "NA" << endl;

//        for (set<string>::iterator si = cache.begin();
//                si != cache.end(); si++) {
//            cout << *si << ' ';
//        }
//        cout << endl;
    }

    return 0;
}