#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <functional>
#include <sstream>

using namespace std;

#define fst first
#define scd second
#define pb push_back
#define mp make_pair
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep(i,x) for(int i=0;i<(int)x;++i)
#define rep1(i,x) for(int i=1;i<=(int)x;++i)
#define rrep(i,x) for(int i=(int)x-1;i>=0;--i)
#define rrep1(i,x) for(int i=(int)x;i>=1;--i)
#define repf(i,a,x) for(int i=a;i<(int)x;++i)
#define repf1(i,a,x) for(int i=a;i<=(int)x;++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

template<typename T> T get(){T a;cin >> a;return a;}
template<typename T> T rev(T & a){reverse(all(a));return a;}

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int inf = 1e9;
const ll linf = 1e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    while (cin >> s, s[0] != '0') {
        map<string, bool> m;

        queue<string> q, r;

        q.push(s);

        int cnt = 0;

        while (q.size()) {
            while (q.size()) {
                string t = q.front(); q.pop();
                if (m[t]) continue;
                m[t] = true;
                bool f = true;
                rep(i, t.size() - 1) {
                    if ((t[i] == 'r' && t[i + 1] == 'b') || (t[i] == 'b' && t[i + 1] == 'r')) {
                        char c = t[i], d = t[i + 1];
                        t[i] = t[i + 1] = 'g';
                        r.push(t);
                        t[i] = c, t[i + 1] = d;
                        f = false;
                    } else if ((t[i] == 'b' && t[i + 1] == 'g') || (t[i] == 'g' && t[i + 1] == 'b')) {
                        char c = t[i], d = t[i + 1];
                        t[i] = t[i + 1] = 'r';
                        r.push(t);
                        t[i] = c, t[i + 1] = d;
                        f = false;
                    } else if ((t[i] == 'r' && t[i + 1] == 'g') || (t[i] == 'g' && t[i + 1] == 'r')) {
                        char c = t[i], d = t[i + 1];
                        t[i] = t[i + 1] = 'b';
                        r.push(t);
                        t[i] = c, t[i + 1] = d;
                        f = false;
                    }
                }
                if (f) {
                    cout << cnt << endl;
                    goto nxt;
                }
            }
            while (r.size()) {
                string t = r.front(); r.pop();
                q.push(t);
            }
            cnt++;
        }

        cout << "NA\n";
nxt:;
    }
}