#include <bits/stdc++.h>

#define ALL(a) (a).begin(). (a).end()

using namespace std;

int other(int x, int y){
	if(x > y)return other(y,x);
	if(x == 0 && y == 1)return 2;
	if(x == 0 && y == 2)return 1;
	if(x == 1 && y == 2)return 0;
}

int main(){
	while(true){
		string str; cin >> str;
		if(str == "0")break;
		vector<int> b(str.size());
		for(int i = 0; i < str.size(); i++){
			switch(str[i]){
				case 'r':
					b[i] = 0;
					break;
				case 'g':
					b[i] = 1;
					break;
				case 'b':
					b[i] = 2;
					break;
			}
		}
		int ans = -1;
		queue<vector<int> > q;
		map<vector<int> , int> m;
		q.push(b);
		m[b] = 0;
		while(!q.empty()){
			auto t = q.front();
			q.pop();
			int c = t[0];
			bool flag = true;
			for(auto e : t){
				if(e != c){
					flag =false;
					break;
				}
			}
			if(flag){
				ans = m[t];
				break;
			}
			
			for(int i = 1; i < t.size(); i++){
				auto tt = t;
				if(t[i] != t[i-1]){
					tt[i] = tt[i-1] = other(t[i], t[i-1]);
				}
				if(m.find(tt) == m.end()){
					q.push(tt);
					m[tt] = m[t]+1;
				}
			}
		}
		if(ans == -1){
			cout << "NA" << endl;
		}
		else{
			cout << ans << endl;
		}
	}

	return 0;
}

