#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cmath>
#include <queue>

#define INF (1 << 21)

using namespace std;

int N;

int check[1000000];

queue<string> que, que_next;

int index(string str){
	
	int ref = 0;
	
	for(int i = 0; i < N; i++){
		ref += str[i] - '0';
		ref *= 3;
	}
	
	return ref;
}

int main(){
	
	while(true){
		string str;
		cin >> str;
		
		queue<string> que_emp;
		
		que = que_emp;
		que_next = que_emp;
		
		for(int i = 0; i < 1000000; i++){
			check[i] = INF;
		}
		
		if(str[0] == '0'){
			break;
		}else{
			N = str.size();
			for(int i = 0; i < N; i++){
				if(str[i] == 'r'){
					str[i] = '0';
				}else if(str[i] == 'b'){
					str[i] = '1';
				}else{
					str[i] = '2';
				}
			}
		}
		
		que.push(str);
		
		int depth = 0;
		
		while(true){
			while(!que.empty()){
				string str = que.front();
				que.pop();
				if(check[index(str)] != INF){
					continue;
				}
				check[index(str)] = depth;
				for(int i = 0; i < N - 1; i++){
					if(str[i] != str[i + 1]){
						string str_copy = str;
						if(str[i] != '0' && str[i + 1] != '0'){
							str_copy[i] = '0';
							str_copy[i + 1] = '0';
						}else if(str[i] != '1' && str[i + 1] != '1'){
							str_copy[i] = '1';
							str_copy[i + 1] = '1';
						}else{
							str_copy[i] = '2';
							str_copy[i + 1] = '2';
						}
						que_next.push(str_copy);
					}
				}
			}
			que = que_next;
			que_next = que_emp;
			depth++;
			if(que.empty()){
				break;
			}
			//cout << depth << " " << que.size() << endl;;
		}
		
		string check_0 = "";
		string check_1 = "";
		string check_2 = "";
		
		for(int i = 0; i < N; i++){
			check_0 = check_0 + "0";
			check_1 = check_1 + "1";
			check_2 = check_2 + "2";
		}
		
		int ans = min(min(check[index(check_0)], check[index(check_1)]), check[index(check_2)]);
		
		if(ans == INF){
			cout << "NA" << endl;
		}else{
			cout << ans << endl;
		}
		
	}
	
	return 0;
}