#include <bits/stdc++.h>

#define FOR(i, n, m) for(int i = (n);i < (m);i++)
#define REP(i, n) for(int i = 0;i < (n);i++)
#define PII pair<int, int>

using namespace std;

string worm;

int all(string a){
    char b = a[0];
    int cnt = 0;
    for(int i = 1;a[i] != '\0';i++){
        if(a[i] != b)
            cnt++;
    }
    return cnt;
}

int solve(){
    queue< pair<string, int> > que;
    map<string, int> m;
    que.push(pair<string, int>(worm, 0));

    if(all(worm) == 0){
        return 0;
    }

    while(que.size()){
        string worm1 = que.front().first;
        int num = que.front().second;
        que.pop();

        if(m[worm1]){
            continue;
        }
        if(all(worm1) == 0){
            return num;
        }

        m[worm1] = num;

        REP(i, worm1.size()-1){
            string tmp = worm1;
            if(tmp[i] != tmp[i+1]){
                if(tmp[i] != 'r' && tmp[i+1] != 'r') tmp[i] = tmp[i+1] = 'r';
                else if(tmp[i] != 'g' && tmp[i+1] != 'g') tmp[i] = tmp[i+1] = 'g';
                else tmp[i] = tmp[i+1] = 'b';

                que.push(pair<string, int> (tmp, num+1));
           }
        }
    }

    return -1;
}

int main(void){
    cin >> worm;
    while(worm[0] != '0'){
        int result = solve();
        if(result >= 0){
            cout << result << endl;
        }else{
            cout << "NA" << endl;
        }
        cin >> worm;
    }

    return 0;
}