#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <map>
#include <queue>
#include <utility>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}
template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

using P = pair<string, int>;

char getLast(char c1, char c2) {
    if (c1 > c2) swap(c1, c2);
    if (c1 == 'b' && c2 == 'g') return 'r';
    if (c1 == 'b' && c2 == 'r') return 'g';
    return 'b';
}

#include <set>
bool check(string s) {
    set<int> st;
    for(auto &c: s) {
        st.insert(c);
    }
    return st.size() == 1;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    while (cin >> s, s != "0") {
        map<string, int> mp;
        int n = s.size();
        queue<P> q;
        q.emplace(s, 0);
        int ans = -1;
        while (q.size()) {
            string e = q.front().first;
            int cnt = q.front().second;
            q.pop();
            if (check(e)) {
                ans = cnt;
                break;
            }
            mp[e] = cnt;
            REP (i, 0, n - 1) {
                if (e[i] != e[i + 1]) {
                    string tmp = e;
                    tmp[i] = tmp[i + 1] = getLast(e[i], e[i + 1]);
                    if (mp.count(tmp) == 0) {
                        q.emplace(tmp, cnt + 1);
                        mp[tmp] = cnt + 1;
                    }
                }
            }
        }
        if (ans == -1) {
            cout << "NA" << endl;
        } else {
            cout << ans << endl;
        }
    }
    return 0;
}

