#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999
int dp[60000];



int main(){
    string s;
    while(cin>>s){
        if(s=="0")break;
        int l=s.size();
        rep(i,60000)dp[i]=INF;
        bool ff=true;
        rep(i,s.size()-1){
            if(s[i]!=s[i+1])ff=false;
        }
        if(ff)cout<<"0"<<endl;
        if(ff)continue;
        int num=0;
        rep(i,s.size()){
            num*=3;
            int p=0;
            if(s[i]=='g')p=1;
            if(s[i]=='b')p=2;
            num+=p;
        }
        dp[num]=0;
        
        queue<pii> que;
        que.push(pii(num,0));
        while(que.size()){
//            cout<<que.size()<<endl;
            pii q=que.front();
            que.pop();
            vector<int> vec;
            rep(i,l){
                vec.pb(q.first%3);
                q.first/=3;
            }
            reverse(all(vec));
            reverse(all(vec));
            rep(i,l-1){
                if(vec[i]!=vec[i+1]){
                    int a=vec[i],b=vec[i+1];
                    if(a>b)swap(a,b);
                    vector<int> v=vec;
                    if(a==0&&b==1)v[i]=v[i+1]=2;
                    if(a==1&&b==2)v[i]=v[i+1]=0;
                    if(a==0&&b==2)v[i]=v[i+1]=1;
                    bool f=true;
                    rep(i,vec.size()-1){
                        if(v[i]!=v[i+1])f=false;
                    }
                    if(f){
                        cout<<q.second+1<<endl;
                        goto next;
                    }
                    int x=0;
                    rep(j,v.size()){
                        x*=3;
                        x+=v[j];
                    }
                    if(dp[x]==INF){
                        dp[x]=q.second+1;
                        que.push(pii(x,q.second+1));
                    }
                }
            }
        }
        cout<<"NA"<<endl;
    next:;
    }
}