#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define MOD 1000000007
#define EPS 1e-10
#define MAX_N 100100
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;
typedef pair<ll, string> PLS;

int ans;
string s;

map<string, int> msi;

void solve(){
	msi[s] = 0;

	queue<string> que;

	que.push(s);

	while (que.size()){
		string ret = que.front();
		que.pop();

		bool f = 0;
		REP(i, ret.size() - 1){
			if (ret[i] != ret[i + 1])break;
			if (i == ret.size() - 2)f = 1;
		}
		if (f){
			ans = min(ans, msi[ret]);
		}

		REP(i, ret.size() - 1){
			string t = ret;
			if (ret[i] != ret[i + 1]){
				if (ret[i] == 'r'&&ret[i + 1] == 'g'){
					t[i] = 'b';
					t[i + 1] = 'b';
				}
				if (ret[i] == 'g'&&ret[i + 1] == 'r'){
					t[i] = 'b';
					t[i + 1] = 'b';
				}
				if (ret[i] == 'r'&&ret[i + 1] == 'b'){
					t[i] = 'g';
					t[i + 1] = 'g';
				}
				if (ret[i] == 'b'&&ret[i + 1] == 'r'){
					t[i] = 'g';
					t[i + 1] = 'g';
				}
				if (ret[i] == 'b'&&ret[i + 1] == 'g'){
					t[i] = 'r';
					t[i + 1] = 'r';
				}
				if (ret[i] == 'g'&&ret[i + 1] == 'b'){
					t[i] = 'r';
					t[i + 1] = 'r';
				}
				if (t == ret)continue;
				if (msi.find(t) == msi.end()){
					//cout << t << endl;
					que.push(t);
				}
				msi[t] = msi[ret] + 1;
			}
		}
	}
}

int main(){
	while (cin >> s&&s != "0"){
		ans = INF;
		msi.clear();
		solve();
		if (ans == INF)cout << "NA" << endl;
		else cout << ans << endl;
	}
}