#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
struct s{
    string worm;
    int nowans;
};
int main(){
    char dc[6][3]={'r','g','b','g','r','b','r','b','g','b','r','g','g','b','r','b','g','r'};
    while(1){
        int che[100000]={0};
        s IN,now;
        queue <s> que;
        cin >> IN.worm;
        IN.nowans=0;
        if(IN.worm[0]=='0')
            break;
        que.push(IN);
        while(1){
            int chenum=0;
            if(que.empty()){
                puts("NA");
                goto exit;
            }
            now=que.front(),que.pop();
            for(int i=0;i<now.worm.size();i++){
                if(now.worm[i]=='r')
                    chenum+=pow(3,i)*0;
                else if(now.worm[i]=='g')
                    chenum+=pow(3,i)*1;
                else if(now.worm[i]=='b')
                    chenum+=pow(3,i)*2;
            }
            if(che[chenum]==1)
                continue;
            else
                che[chenum]=1;
            for(int i=0;i<now.worm.size()-1;i++){
                if(now.worm[i]!=now.worm[i+1])
                    break;
                if(i==now.worm.size()-1-1){
                    printf("%d\n",now.nowans);
                    goto exit;
                }
            }
            for(int i=0;i<now.worm.size()-1;i++){
                if(now.worm[i]!=now.worm[i+1]){
                    for(int j=0;j<6;j++){
                        if(now.worm[i]==dc[j][0]&&now.worm[i+1]==dc[j][1]){
                            now.worm[i]=dc[j][2],now.worm[i+1]=dc[j][2],now.nowans++;
                            que.push(now);
                            now.worm[i]=dc[j][0],now.worm[i+1]=dc[j][1],now.nowans--;
                        }
                    }
                }
            }
        }
exit:;
    }
    return 0;
}