#include<iostream>
#include<string>
#include<queue>
#include<set>
#define psi pair<string, int>

using namespace std;

bool check(string str){
    return (str[0]!=str[1]);
}

bool same(string str){
    for(int i=0; i<str.size(); i++){
        if(str[0]!=str[i]) return false;
    }
    return true;
}

char getColor(string str){
    char c1=min(str[0], str[1]);
    char c2=max(str[0], str[1]);
    if(c1=='b'&&c2=='g') return 'r';
    if(c1=='b'&&c2=='r') return 'g';
    if(c1=='g'&&c2=='r') return 'b';
}
int solve(string str){
    queue<psi> qu;
    qu.push(psi(str, 0));
    set<string> done;

    while(!qu.empty()){
        psi w=qu.front(); qu.pop();
        string s=w.first;
        done.insert(s);

        if(same(s)){
            return w.second;
        }

        for(int i=0; i<s.size()-1; i++){
            if(check(s.substr(i, 2))){
                char new_color=getColor(s.substr(i, 2));
                string nx=s;
                nx[i+1]=nx[i]=new_color;
                if(done.count(nx)==1) continue;
                //cout<< nx<< endl;
                qu.push(psi(nx, w.second+1));
                done.insert(nx);
            }
        }
    }
    return -1;
}
int main(){

    while(1){
        string s;
        cin>> s;
        if(s=="0") break;

        int ans=solve(s);
        if(ans==-1){
            cout<< "NA"<< endl;
        }else{
            cout<< ans<< endl;
        }
    }

    return 0;
}