#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
    return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
    os<<'[';
    rep(i,a.size()) os<<(i?" ":"")<<a[i];
    return os<<']';
}

char color(char a, char b) {
    if (a > b) swap(a, b);
    if (a == 'b') {
        if (b == 'g') return 'r';
        if (b == 'r') return 'g';
    }
    return 'b';
}

int main() {
    for(string worm; cin >> worm, worm != "0"; ) {
        int len = worm.size();
        queue<string> que;
        set<string> dist;
        que.push(worm);
        for(int time = 0; ; time++) {
            queue<string> que2;
            while(!que.empty()) {
                string w = que.front();
                que.pop();
                if (dist.count(w) == 1) continue;
                dist.insert(w);
                int cnt = 0;
                rep(i, len - 1) {
                    if (w[i] == w[i + 1]) {
                        cnt++;
                        continue;
                    }
                    char c = color(w[i], w[i + 1]);
                    string t = w;
                    t[i] = t[i + 1] = c;
                    que2.push(t);
                }
                if (cnt == len - 1) {
                    cout << time << endl;
                    goto end;
                }
            }
            if (que2.empty()) {
                cout << "NA" << endl;
                goto end;
            }
            que = que2;
        }
end:;
    }
    
    return 0;
}