#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
//#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second

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

const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
string str;
string t;
string tmp;
int count;

int main(){
	while(cin >> str){
		map<string,int> mp;
		mp[str] = 0;
		if(str == "0"){
			break;
		}
		queue<string> q;
		q.push(str);

		char a[5] = {'r','g','b'};
		bool q_flag = true;

		while(!q.empty()){
			tmp = q.front();
			q.pop();
			bool flag = true;

			for(int i=0; i+1<tmp.size(); i++){
				if(tmp[i] != tmp[i+1]){
					flag = false;
					for(int j=0; j<3; j++){
						if(a[j] != tmp[i] && a[j] != tmp[i+1]){
							t = tmp;
							t[i+1] = a[j];
							t[i] = a[j];
							if(mp.count(t) == 1){
								continue;
							}
							mp[t] = mp[tmp] + 1;
							q.push(t);
						}
					}
				}
			}
			if(flag == true){
				cout << mp[tmp] << endl;
				q_flag = false;
				break;
			}
		}

		if(q_flag == true){
			cout << "NA" << endl;
		}

	}

}