#include <cstdio>
#include <queue>
#include <map>

using namespace std;

int main()
{
	char str[256];
	char col[3] = "rgb";
	
	while (scanf("%s", str) && str[0] !='0'){
		map<string, int> minTime;
		queue<string> q;
		string s = str;
		
		minTime[s] = 0;
		
		bool ng = true;
		for (q.push(s); !q.empty(); q.pop()){
			string look = q.front();
			
			bool flag = true;
			for (int i = 0; i < look.size() - 1; i++){
				if (look[i + 1] != look[i]) flag = false;
			}
			
			if (flag){
				printf("%d\n", minTime[look]);
				ng = false;
				break;
			}
			
			for (int c = 0; c < 3; c++){
				for (int i = 0; i < look.size() - 1; i++){
					if (look[i + 1] != col[c] && look[i] != col[c] && look[i + 1] != look[i]){
						string next = look;
						next[i + 1] = next[i] = col[c];
						if (minTime.count(next) > 0) continue;
						minTime[next] = minTime[look] + 1;
						q.push(next);
					}
				}
			}
		}
		if (ng) printf("NA\n");
	}
	
	return (0);
}