#include <iostream>
#include <queue>
#include <map>

using namespace std;

int solve(string s)
{
    map<string, int> mem;
    queue<pair<string, int> > q;

    q.push(pair<string, int>(s, 0));
    mem[s] = 0;

    while (!q.empty()) {
        pair<string, int> tmp;
        bool flag = true;

        tmp = q.front();
        q.pop();

        // Check
        for (int i = 1; i < tmp.first.size(); i++)
            if (tmp.first[0] != tmp.first[i]) {
                flag = false;
                break;
            }
        if (flag) 
            return tmp.second;

        for (int i = 0; i < tmp.first.size() - 1; i++) {
            if (tmp.first[i] != tmp.first[i + 1]) {
                string str = tmp.first;
                int num = (int)(tmp.first[i] + tmp.first[i + 1]);

                if (num == 217) 
                    str[i] = str[i + 1] = 'b';
                else if (num == 212) 
                    str[i] = str[i + 1] = 'g';
                else if (num == 201) 
                    str[i] = str[i + 1] = 'r';

                if (mem.count(str) == 0) {
                    q.push(pair<string, int>(str, tmp.second + 1));
                    mem[str] = tmp.second + 1;
                }
            }
        }
    }
    return -1;
}

int main()
{
    string inp;

    while (cin >> inp, inp != "0") {
        int num = solve(inp);

        if (num >= 0)
            cout << num << endl;
        else 
            cout << "NA" << endl;
    }

    return 0;
}