#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>

using namespace std;

typedef pair<string, int> psi;

bool check(string worm) {
    for (int i = 1; i < worm.size(); i++) {
        if (worm[i] != worm[i-1]) return false;
    }
    return true;
}

char change_color(char a, char b) {
    char c;
    if (a == 'r') {
        if (b == 'g') c = 'b';
        else c = 'g';
    }
    if (a == 'g') {
        if (b == 'r') c = 'b';
        else c = 'r';
    }
    if (a == 'b') {
        if (b == 'r') c = 'g';
        else c = 'r';
    }
    return c;
}

int solve(string worm) {
    int ans = -1;
    map<string, int> memo;
    queue<psi> Q;

    Q.push(make_pair(worm, 0));
    while(!Q.empty()) {
        psi now = Q.front(); Q.pop();
        if (check(now.first)) {
            return now.second;
        }
        if (memo[now.first]) continue;
        memo[now.first] = now.second;

        for (int i = 1; i < now.first.size(); i++) {
            if (now.first[i] == now.first[i-1]) continue;
            char color = change_color(now.first[i-1], now.first[i]);
            string next = now.first;
            next[i-1] = next[i] = color;

            Q.push(make_pair(next, now.second + 1));
        }
    }
    return ans;
}


int main() {
    string worm;
    while(cin >> worm) {
        if (worm == "0") break;
        int ans = solve(worm);
        if (ans == -1)
            cout << "NA" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

