#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <queue>
using namespace std;

int main() {
	string sin,ans;
	while(cin >> sin && sin != "0"){
		queue<string> Q;
		map<string,int> B;
		ans = "";
		Q.push(sin);
		B[sin] = 0;
		while(!Q.empty()){
			string s = Q.front();Q.pop();
			char t = s[0];
			bool allF = true;
			for(int i = 0;i<s.length();i++){
				if(s[i] != t){
					allF = false;
					break;
				}
			}
			if(allF){
				ans = s;
				break;
			}
			for(int i = 1;i<s.length();i++){
				string ss = s;
				if(s[i] != s[i-1]){
					char c = 'r' + 'g' + 'b' - s[i] - s[i-1];
					ss[i] = c;
					ss[i-1] = c;
					if(B[ss] == 0){
						B[ss] = B[s] + 1;
						Q.push(ss);
					}
				}
			}
		}
		if(!ans.empty()){
			cout << B[ans] << endl;
		}
		else{
			cout << "NA" << endl;
		}
	}
	return 0;
}