#include<iostream>
#include<cstdio>
#include<map>
#include<queue>

using namespace std;

class wormcheck{
    public:
    string Worm;
    int Val;
    wormcheck(string W,int V){
        Worm=W;
        Val=V;
    }
};

int main(){
    string worm;
    while(cin>>worm){
        if(worm=="0")break;
        queue<wormcheck> que;
        que.push(wormcheck(worm,0));
        map<string,int> visit;
        while(1){
            if(que.empty()){cout<<"NA"<<endl;break;}
            wormcheck w = que.front();
            que.pop();
            if(visit[w.Worm]==1)continue;
            visit[w.Worm]=1;
            for(int i=1;i<w.Worm.size();i++){
                if(w.Worm[i]!=w.Worm[i-1]){
                    goto Skip;
                }
            }
            //printf("%s %d",w.Worm,w.Val);
            cout<<w.Val<<endl;
            break;
            Skip:;
            string subWorm = w.Worm;
            for(int i=1;i<w.Worm.size();i++){
                if(subWorm[i]!=subWorm[i-1]){
                    if(subWorm[i]!='b'&&subWorm[i-1]!='b'){
                        subWorm[i]='b';
                        subWorm[i-1]='b';
                    }
                    else if(subWorm[i]!='g'&&subWorm[i-1]!='g'){
                        subWorm[i]='g';
                        subWorm[i-1]='g';
                    }
                    else if(subWorm[i]!='r'&&subWorm[i-1]!='r'){
                        subWorm[i]='r';
                        subWorm[i-1]='r';
                    }
                    que.push(wormcheck(subWorm,w.Val+1));
                    subWorm=w.Worm;
                }
            }
        }

    }
    return 0;
}