//2013-5

#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <time.h>
#define mp make_pair
#define fs first
#define sc second
#define rep(x,n) for(int x = 0;x < n;x ++)
#define Rep(x,n) for(int x = 1;x <= n;x ++)
using namespace std;

char retcol(char c1,char c2){
    if((c1 == 'g' && c2== 'r')||(c1 == 'r' && c2== 'g'))
        return 'b';
    else if((c1 == 'b' && c2 == 'r')||(c1 == 'r' && c2 == 'b'))
        return 'g';
    else
        return 'r';
}

int n;

bool issame(string xx){
    int nu = xx.size();
    rep(i,nu-1)
        if(xx[i]!=xx[i+1])
            return 0;
    return 1;
}

int main(){

    bool tf = 0;
    string str,next;
    while(cin >> str&&str != "0"){
        queue<string> que;
        que.push(str);
        tf = 0;
        n = str.size();
        //この時点で判定
        if(issame(str)){
            printf("0\n");
            continue;
        }
        map<string,int> flag;
        flag.insert(make_pair(str,0));
        //探索
        while(!que.empty()&& tf == 0){
            string str = que.front();
            que.pop();
            if(flag.find(str)==flag.end())
                continue;
            int num = flag.find(str)->second;
            rep(i,n-1){
                if(str[i]!=str[i+1]){
                    next = str;
                    next[i]=retcol(str[i],str[i+1]);
                    next[i+1]=next[i];
                    if(issame(next)){
                        tf = 1;
                        cout << num + 1 << endl;
                        break;
                    }
                    if(flag.find(next)==flag.end()){
                        que.push(next);
                        flag.insert(make_pair(next,num+1));
                    }
                    
                }
            }
        }
        if(tf == 0){
            printf("NA\n");
        }
    }
}