#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    string color = "rgb";

    for(;;){
        string s;
        cin >> s;
        if(s == "0")
            return 0;
        int n = s.size();

        set<string> worm;
        queue<pair<string, int> > q;
        worm.insert(s);
        q.push(make_pair(s, 0));
        int ok = false;
        while(!q.empty()){
            s = q.front().first;
            int k = q.front().second;
            q.pop();

            ok = true;
            for(int i=1; i<n; ++i){
                if(s[i] != s[i-1]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                cout << k << endl;
                break;
            }

            for(int i=1; i<n; ++i){
                if(s[i] == s[i-1])
                    continue;
                for(int j=0; j<3; ++j){
                    if(s[i] != color[j] && s[i-1] != color[j]){
                        string s1 = s;
                        s1[i] = s1[i-1] = color[j];
                        if(worm.find(s1) == worm.end()){
                            worm.insert(s1);
                            q.push(make_pair(s1, k+1));
                        }
                    }
                }
            }
        }

        if(!ok)
            cout << "NA" << endl;
    }
}