#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

struct W
{
	string s;
	int num;
	
	W(string s = "",int num = 0) : s(s),num(num) {}
};

char change(char a,char b)
{
	if((a == 'r' && b == 'g') || (a == 'g' && b == 'r'))
	{
		return 'b';	
	}
	else if((a == 'r' && b == 'b') || (a == 'b' && b == 'r'))
	{
		return 'g';
	}
	else if((a == 'g' && b == 'b') || (a == 'b' && b == 'g'))
	{
		return 'r';
	}
	return 'N';
}

int main()
{
	string s;
	while(cin >> s)
	{
		if(s == "0") break;
		
		string t = "",t2 = "",t3 = "";
		rep(i,s.size())
		{
			t += "r";
			t2 += "g";
			t3 += "b";
		}

		queue<W> que;
		que.push(W(s,0));
		map<string,int> m;
		int ans = 0;
		bool flag = true;

		while(!que.empty())
		{
			W w = que.front();
			que.pop();

			if(m[w.s] > 0) 
			{
				continue;
			}

			if(w.s == t || w.s == t2 || w.s == t3)
			{
				flag = false;
				ans = w.num;
				break;
			}

			m[w.s] = w.num;

			rep(i,s.size()-1)
			{
				string temp = w.s;
				if(change(w.s[i],w.s[i+1]) == 'N') continue;
				
				temp[i] = temp[i+1] = change(w.s[i],w.s[i+1]);
				que.push(W(temp,w.num+1));
			}
		}
		if(flag) cout << "NA" << endl;
		else cout << ans << endl;
	}

	return 0;
}