#include <bits/stdc++.h>
using namespace std;

bool check(string& str)
{
	for (int i = 1; i < str.size(); i++){
		if (str[i] != str[0]) return false;
	}
	return true;
}

int main()
{
	string str;
	while (cin >> str, str != "0"){
		queue<pair<string, int> > que;
		que.push({str, 0});
		set<string> done;
		int res = -1;
		while (!que.empty()){
			auto p = que.front(); que.pop();
			//cout << p.first << endl;
			if (check(p.first)){
				res = p.second;
				break;
			}
			if (done.count(p.first)) continue;
			done.insert(p.first);
			
			for (int i = 1; i < p.first.size(); i++){
				if (p.first[i] != p.first[i - 1]){
					int cnt[256] = {0};
					cnt[p.first[i]]++;
					cnt[p.first[i - 1]]++;
					
					string tmp = p.first;
					if (!cnt['r']){
						tmp[i] = tmp[i - 1] = 'r';
					}
					else if (!cnt['g']){
						tmp[i] = tmp[i - 1] = 'g';
					}
					else {
						tmp[i] = tmp[i - 1] = 'b';
					}
					
					que.push({tmp, p.second + 1});
				}
			}
		}
		if (res == -1) puts("NA");
		else printf("%d\n", res);
	}
	
	return 0;
}