#include <iostream>
#include <string>
#include <queue>
#include <map>

using namespace std;



int main()
{
    map<string, string> ct;
    ct["rr"] = "rr";
    ct["rb"] = "gg";
    ct["rg"] = "bb";

    ct["gr"] = "bb";
    ct["gg"] = "gg";
    ct["gb"] = "rr";

    ct["br"] = "gg";
    ct["bg"] = "rr";
    ct["bb"] = "bb";

    map<string, bool> dt;
    dt["rr"] = true;
    dt["gg"] = true;
    dt["bb"] = true;
    
    for(;;) {
        string in;
        cin >> in;

        if ( in == "0" )
            break;

        std::map<string, bool> correct;
        correct[string(in.size(), 'r')] = true;
        correct[string(in.size(), 'g')] = true;
        correct[string(in.size(), 'b')] = true;

        int result_times = 0;

        queue<pair<int, string> > q;
        q.push( make_pair( 0, in ) );

        map<string, bool> memo;
        bool goal = false;

        // loop
        while( !q.empty() ) {
            int const times = q.front().first;
            string const s = q.front().second;
            q.pop();

            //cout << gtimes << endl;
            if ( correct[s] ) {
                goal = true;
                result_times = times;
                break;
            } 

            //cout << "---" << endl;
            for( size_t i=0; i<s.size()-1; ++i ){
                string const pa = s.substr( i, 2 );
                string const t = s.substr( 0, i ) + ct[pa] + s.substr( i + 2 );

                if ( t == s )
                    continue;
                if ( memo[t] )
                    continue;

                memo[t] = true;

                q.push( make_pair( times + 1, t ) );
                //cout << t << endl;
            }
        }

        // put
        if ( goal ) {
            cout << result_times << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}