#define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 30;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)


int memo[1 << 20];
int w[10];
int f[3];

void make_f(int n){
	rep(i, 3){
		int num = 0;
		rep(j, n){
			num = num * 4 + i;
		}
		f[i] = num;
	}
}

int get_s(const string &s){
	int res = 0;
	rep(i, s.size()){
		res *= 4;
		if(s[i] == 'r') res++;
		if(s[i] == 'g') res += 2;
	}
	return res;
}

int get_color(int a, int b){
	int c = min(a, b);
	int d = max(a, b);
	if(c == 0 && d == 1) return 2;
	if(c == 0 && d == 2) return 1;
	else return 0;
}

int get_num(int *w, int n){
	int res = 0;
	for(int i = 0; i < n; i++){
		res = res * 4 + w[i];
	}
	return res;
}

void to_w(int num, int n){
	for(int i = 0; i < n; i++){
		w[i] = num % 4;
		num /= 4;
	}
	reverse(w, w + n);
}

int main(){
	int n, start;
	string s;
	while(cin >> s && s != "0"){
		memset(memo, -1, sizeof(memo));
		n = s.size();
		start = get_s(s);
		make_f(n);
		queue<int> que;
		que.push(start);
		memo[start] = 0;
		bool ok = false;
		while(!que.empty()){
			int num = que.front();
			int c = memo[num];
			que.pop();
			if(num == f[0] || num == f[1] || num == f[2]){
				cout << c << endl;
				ok = true;
				break;
			}
			to_w(num, n);
			rep(i, n-1){
				if(w[i] != w[i+1]){
					int a = w[i];
					int b = w[i+1];
					w[i] = get_color(a, b);
					w[i+1] = get_color(a, b);
					int num2 = get_num(w, n);
					if(memo[num2] == -1){
						memo[num2] = c + 1;
						que.push(num2);
					}
					w[i] = a;
					w[i+1] = b;
				}
			}
		}
		if(!ok) cout << "NA" << endl;
	}
	return 0;
}