#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

struct state {
    string worm;
    int count;

    state(string a, int b): worm(a), count(b) {}
};

char change_to(char a, char b) {
    if (a > b) swap(a, b);
    if (a == 'b' && b == 'g') return 'r';
    if (a == 'b' && b == 'r') return 'g';
    return 'b';
}

int main() {
    string S;
    while (true) {
        cin >> S;
        if (S == "0") break;
        
        set<string> visited;
        queue<state> que;

        int ans = -1;

        que.emplace(S, 0);
        while (!que.empty()) {
            state st = que.front(); que.pop();

            if (visited.find(st.worm) != end(visited))
                continue;
            visited.insert(st.worm);

            string worm = st.worm;

            bool ok = true;
            for (int j = 1; j < worm.size(); ++j) {
                if (worm[j] != worm[0]) {
                    ok = false; break;
                }
            }
            
            if (ok) {
                ans = st.count;
                break;
            }

            visited.insert(worm);
            for (int j = 0; j < worm.size()-1; ++j) {
                if (worm[j] != worm[j+1]) {
                    char c1 = worm[j], c2 = worm[j+1];
                    worm[j] = worm[j+1] = change_to(worm[j], worm[j+1]);
                    que.emplace(worm, st.count+1);
                    worm[j] = c1, worm[j+1] = c2;
                }
            }
        }

        if (ans == -1) {
            cout << "NA" << endl;
        } else {
            cout << ans << endl;
        }
    }
    return 0;
}