#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<string, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};

int main(){
    while(1){
        string s; cin>>s;
        if(s == "0") return 0;

        queue<P> que;
        que.push(P(s, 0));
        map<string, bool> visited;
        visited[s] = true;
        bool valid = false;
        while(que.size()){
            string t;
            int cnt;
            tie(t, cnt) = que.front();
            que.pop();

            bool allR = true, allB = true, allG = true;
            for(int i=0; i<t.size(); i++){
                if(t[i] == 'r'){
                    allB = false;
                    allG = false;
                }
                if(t[i] == 'b'){
                    allR = false;
                    allG = false;
                }
                if(t[i] == 'g'){
                    allR = false;
                    allB = false;
                }
            }

            if(allR || allB || allG){
                valid = true;
                cout << cnt << endl;
                break;
            }

            for(int i=0; i<t.size()-1; i++){
                bool R = true, B = true, G = true;

                if(t[i] != t[i+1]){
                    if(t[i] == 'r' || t[i+1] == 'r') R = false;
                    if(t[i] == 'b' || t[i+1] == 'b') B = false;
                    if(t[i] == 'g' || t[i+1] == 'g') G = false;

                    if(R){
                        string r = t;
                        r[i] = 'r';
                        r[i+1] = 'r';

                        if(!visited[r]){
                            que.push(P(r, cnt+1));
                            visited[r] = true;
                        }
                    }
                    if(B){
                        string b = t;
                        b[i] = 'b';
                        b[i+1] = 'b';

                        if(!visited[b]){
                            que.push(P(b, cnt+1));
                            visited[b] = true;
                        }
                    }
                    if(G){
                        string g = t;
                        g[i] = 'g';
                        g[i+1] = 'g';

                        if(!visited[g]){
                            que.push(P(g, cnt+1));
                            visited[g] = true;
                        }
                    }
                }
            }
        }

        if(!valid){
            cout << "NA" << endl;
        }
    }
}


Measured memory_bytes: 4836