#include <bits/stdc++.h>

using namespace std;

bool check(string s){
    for(int i=0; i< s.size()-1; i++) if(s[i] != s[i+1]) return false;
    return true;
}

int main(){
    string s;
    while(cin >> s, s!= "0"){
        queue<pair<string, int> > que;
        que.push(make_pair(s, 0));
        int ret = 100;

        map<string, int> m;
        while(que.size()){
            s = que.front().first; int count = que.front().second; que.pop();

            if(ret < count) continue;
            if(check(s))ret = count;

            if(m[s] == 0 || count+1 < m[s]){
                string tmp = s;
                m[s] = count+1;
                string t = "rgb";
                vector<int> v(3); v[0] = 0; v[1] = 1; v[2] = 2;
                map<string, int> mp; mp["r"] = 0; mp["g"] = 1; mp["b"] = 2;
                do{
                    for(int i=0; i< s.size(); i++){
                        s[i] = t[v[mp[s.substr(i, 1)]]];
                    }
                    m[s] = count+1;
                }while(next_permutation(v.begin(), v.end()));
                s = tmp;
            }
            else continue;

            for(int i=0; i< s.size()-1; i++){
                if(s[i] != s[i+1]){
                    string t = s.substr(i, 2);
                    sort(t.begin(),t.end());
                    if(t == "br") t = "gg";
                    else if(t == "bg") t = "rr";
                    else if(t == "gr") t = "bb";
                    que.push(make_pair(s.substr(0, i)+t+s.substr(i+2), count+1));
                }
            }
        }
        if(ret == 100) cout << "NA" << endl;
        else cout << ret << endl;
    }
}