#include <iostream>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <map>
using namespace std;

void bfs(string worm);
char jump(char c1, char c2);
int main(int argc, char const* argv[])
{
    string worm;
    while ( cin >> worm ) {
        if( worm == "0" ) { break; }
        else
        {
            bfs(worm);
        }
    }
    return 0;
}


void bfs(string worm){
    //puts("enter bfs");
    queue<string> q;
    string str;
    map<string, int> dis;
    q.push(worm); 
    dis[worm] = 0;

    while ( q.size() != 0 ) 
    {
        //puts("enter while");
        //一つ取り出す
        str = q.front(); q.pop();

        //終了判定
        bool is_same = true;
        for( int i=0; i<str.length()-1; i++)
        {
            //cout << 
            if( str[i] != str[i+1]) { is_same = false; continue; }
        }
        if ( is_same == true ) 
        {
            cout << dis[str] << endl;
            return;
        }
        //cout<<"worm:" << worm<< endl;
        //cout<<"str:" << str << endl;
        //cout<<"time:" << time << endl;

        //色が違ったらpush
        for(int i=0; i<str.size()-1; i++){
            //隣が色違い
            //puts("enter while");
            if( str[i] != str[i+1])
            {
                string next_str = str;
                next_str[i] = next_str[i+1] = jump(str[i], str[i+1]);
                //まだ通ってない
                if ( dis.find(next_str) == dis.end() )
                {
                    q.push(next_str);
                    dis[next_str] = dis[str] + 1;
                }
                else { continue; }
            }
        }
    }
    cout << "NA" << endl;
}

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