#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <iterator>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())

typedef unsigned long long ull;
const int INF = (int)1e8;

int n;
int mp[1<<20];

int tohash(string &s){
	int a = 0;
	FOR(i,n){
		a *= 4;
		if(s[i] == 'r') a += 1;
		else if(s[i] == 'g') a += 2;
		else a += 3;
	}
	return a;
}

int decodeC(int hash,int i){
	return (hash >> (2*i)) & 3;
}

bool OK(int hash){
	int c = decodeC(hash,0);
	for(int i = 1; i < n; i++)
		if(decodeC(hash,i) != c) return false;
	return true;
}

void setC(int& hash,int i,int v){
	hash = (hash & ~(3 << (2*i))) | (v << (2*i));
}

typedef pair<int,int> P;

int main(){
	string s;
	while(cin>>s,s!="0"){
		n = sz(s);
		memset(mp,0x7F,sizeof(mp));
		mp[tohash(s)] = 0;

		int ans = -1;

		priority_queue<P,vector<P>,greater<P> > q;
		q.push(P(0,tohash(s)));

		while(!q.empty()){
			P p = q.top(); q.pop();
			int v = p.second;
			if(mp[v] < p.first) continue;

			if(OK(v)){
				ans = p.first;
				break;
			}

			for(int i = 0; i < n-1; i++){
				int hash = p.second;
				int c = decodeC(hash , i) ^ decodeC(hash, i + 1);
				if(c == 0) continue;
				setC(hash,i,c);
				setC(hash,i+1,c);
				if(mp[hash] > p.first + 1){
					mp[hash] = p.first + 1;
					q.push(P(p.first + 1,hash));
				}
			}
		}

		if(ans == -1) puts("NA");
		else cout << ans << endl;
	}
	return 0;
}