#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
class Data{
public:
    string bc;
    int t;
    Data(string bc,int t):bc(bc),t(t){}
    Data(){}
};
bool judge(string s,int l){
    for(int i=0;i<l-1;++i){
        if(s[i]!=s[i+1])return false;
    }
    return true;
}
char cj(char a,char b){
    if(a=='b'&&b=='g')return 'r';
    if(a=='b'&&b=='r')return 'g';
    if(a=='g'&&b=='r')return 'b';
    swap(a,b);
    if(a=='b'&&b=='g')return 'r';
    if(a=='b'&&b=='r')return 'g';
    if(a=='g'&&b=='r')return 'b';
}
int main()
{
    string s;
    while(cin>>s,s!="0")
    {
        int l=s.length();
        int res=-1;
        queue<Data> Q;
        set<string> visited;
        Q.push(Data(s,0));
        while(!Q.empty())
        {
            Data t=Q.front();
            Q.pop();
            if(visited.count(t.bc))continue;
            if(judge(t.bc,l)){
                res=t.t;
                break;
            }
            visited.insert(t.bc);
            for(int i=0;i<l-1;++i){
                if(t.bc[i]==t.bc[i+1])continue;
                char nc=cj(t.bc[i],t.bc[i+1]);
                string nbc=t.bc;
                nbc[i]=nbc[i+1]=nc;
                Q.push(Data(nbc,t.t+1));
            }
        }
        if(res==-1)
                cout<<"NA"<<endl;
        else
                cout<<res<<endl;
    }
    return 0;
}