#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define INF 100000000
typedef long long ll;

int main(void) {
    while (1) {
        string s;
        cin >> s;
        if (s == "0") break;
        map<string, int> mi;
        queue<string> q;
        q.push(s);
        mi[s] = 0;
        bool flag = true;
        while (!q.empty()) {
            string now = q.front(); q.pop();
            // 全て同じ文字かどうかのチェック
            int i;
            for (i = 0; i < now.size()-1; i++) {
                if (now[i] != now[i+1]) {
                    break;
                }
            }
            if (i == now.size()-1) {
                cout << mi[now] << endl;
                flag = false;
                break;
            }
            // いろいろ移行するところを考える
            for (int i = 0; i < now.size()-1; i++) {
                string s = now;
                if (s[i] != s[i+1]) {
                    if (s[i] != 'r' && s[i+1] != 'r') {
                        s[i] = 'r'; s[i+1] = 'r';
                    } else if (s[i] != 'g' && s[i+1] != 'g') {
                        s[i] = 'g'; s[i+1] = 'g';
                    } else {
                        s[i] = 'b'; s[i+1] = 'b';
                    }
                }
                if (mi.find(s) == mi.end()) {
                    q.push(s);
                    mi.insert(map<string, int>::value_type(s, mi[now]+1));
                }
            }
        }
        if (flag) cout << "NA" << endl;
    }
    return 0;
}