#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>

using namespace std;

typedef vector<int> vi;

inline bool ok(const vi & v){
    for (int i = 1; i < v.size(); i++){
        if (v[i] != v[0]) return false;
    }
    return true;
};

struct state {
    vi v;
    int n;
};

int main(){
    string s;
    while (cin >> s, s != "0"){
        vi init(s.size());
        for (int i = 0; i < s.size(); i++){
            if (s[i] == 'r') init[i] = 0;
            else if (s[i] == 'g') init[i] = 1;
            else init[i] = 2;
        }
        queue<state> q;
        set<vi> dp;
        q.push({ init, 0 });

        int ans = -1;
        while (q.size()){
            state sta = q.front();
            q.pop();
            vi & sv = sta.v;
            auto pr = dp.insert(sv);
            if (!pr.second){
                continue;
            }
            if (ok(sv)){
                ans = sta.n;
                break;
            }
            for (int i = 1; i < sv.size(); i++){
                if (sv[i] != sv[i - 1]){
                    int a = sv[i];
                    int b = sv[i - 1];
                    sv[i] = sv[i - 1] = 3 - (a + b);
                    q.push({ sv, sta.n + 1 });
                    sv[i] = a;
                    sv[i - 1] = b;
                }
            }
        }
        if (ans == -1){
            cout << "NA" << endl;
        }
        else{
            cout << ans << endl;
        }
    }
}