#include <vector>
#include <list>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>
#include <complex>
#include <iostream>
#include <iterator>

using namespace std;

#define reps(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reps(i, 0, n) 

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	char str[16];
	while(scanf("%s", str), str[0]!='0'){
		int n = strlen(str);
		int ans = -1;
		set<string> visited;
		queue<pair<string, int> > Q;
		Q.push(make_pair(str, 0));
		while(!Q.empty()){
			pair<string, int> data = Q.front();
			Q.pop();
			if(visited.count(data.first))
				continue;
			if(count(data.first.begin(), data.first.end(), data.first[0]) == n){
				ans = data.second;
				break;
			}
			visited.insert(data.first);
			rep(i, n-1){
				char a = min(data.first[i], data.first[i+1]);
				char b = max(data.first[i], data.first[i+1]);
				if(a == b)
					continue;
				char nc;
				if(a == 'b')
					nc = b=='g' ? 'r' : 'g';
				else
					nc = 'b';
				string next = data.first;
				next[i] = next[i+1] = nc;
				Q.push(make_pair(next, data.second+1));
			}
		}
		if(ans == -1)
			puts("NA");
		else
			printf("%d\n", ans);
	}
	return 0;
}