#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <sstream>
using namespace std;

int ar[11], ag[11], ab[11];
bool checked[59049];
int p3[11];
map<int,int> change = {
    {0,0}, {1,8}, {2,4}, {3,8}, {4,4}, {5,0}, {6,4}, {7,0}, {8,8}
};

int conv(string s) {
    int ret = 0;
    for (int i=0; i<(int)s.size(); ++i) {
        ret *= 3;
        if (s[i] == 'g') ret += 1;
        if (s[i] == 'b') ret += 2;
    }
    return ret;
}

int rotate(int x, int n) {
    int ret = 0;
    for (int i=0; i<n; ++i) {
        ret = ret * 3 + (x % 3 + 1) % 3;
        x /= 3;
    }
    return ret;
}

int main() {
    p3[0] = 1;
    for (int i=1; i<=10; ++i) {
        p3[i] = p3[i-1] * 3;
    }
    ar[0] = ag[0] = ab[0] = 0;
    for (int i=1; i<=10; ++i) {
        ar[i] = ar[i-1];
        ag[i] = ag[i-1] * 3 + 1;
        ab[i] = ab[i-1] * 3 + 2;
    }
    string s;
    while (cin >> s, s != "0") {
        memset(checked, false, sizeof checked);
        int n = s.size();
        int first = conv(s);
        queue<pair<int,int> > q;
        q.push(make_pair(first, 0));
        checked[first] = true;
        int res = -1;
        while ( ! q.empty()) {
            int col = q.front().first;
            int t = q.front().second;
            q.pop();
            if (col == ar[n] || col == ag[n] || col == ab[n]) {
                res = t;
                break;
            }
            for (int i=0; i<n-1; ++i) {
                int replace = change[(col / p3[i]) % 9];
                int nx = (col / p3[i+2]) * p3[i+2] + replace * p3[i] + (col % p3[i]);
                if ( ! checked[nx]) {
                    q.push(make_pair(nx, t+1));
                    checked[nx] = true; nx = rotate(nx, n);
                    checked[nx] = true; nx = rotate(nx, n);
                    checked[nx] = true;
                }
            }
        }
        if (res < 0) {
            cout << "NA" << endl;
        } else {
            cout << res << endl;
        }
    }
    return 0;
}