#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
string s;
string rbg = "rbg";
char calc(char a, char b)
{
    for(int i = 0; i < rbg.size(); i++) if(rbg[i] != a and rbg[i] != b) return rbg[i];
}
bool check(string s)
{
    char ch = s[0];
    for(int i = 0; i < s.size(); i++) if(ch != s[i]) return false;
    return true;
}
int solve()
{
    map<string, int> mp;
    queue<pair<string, int>> que;
    que.push(make_pair(s, 0));
    while(que.size())
    {
        pair<string, int> p = que.front(); que.pop();
        string target = p.first;
        int cnt = p.second;
        if(mp.count(target)) continue;
        if(check(target)) return cnt;
        mp[target] = cnt;
        int pos = 0;
        while(pos < target.size() - 1)
        {
            string next_target = target;
            char a = next_target[pos], b = next_target[pos + 1];
            if(a != b)
            {
                next_target[pos] = next_target[pos + 1] = calc(a, b);
                que.push(make_pair(next_target, cnt + 1));
            }
            pos++;
        }
    }
    return -1;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> s, s != "0")
    {
        int ans = solve();
        if(ans == -1) cout << "NA" << endl;
        else cout << ans << endl;
    }
    return 0;
}


