
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
 
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define MCLR(a) memset((a), -1 ,sizeof(a))
#define SZ(a) (sizeof(a))
#define FILL(a,v) fill((int*)a,(int*)(a+(SZ(a)/SZ(*(a)))),v)
#define dump(x)  cerr << #x << " = " << (x) << endl

bool cheak(int x,int y,int xMax,int yMax)
{return x >= 0 && y >= 0 && xMax > x && yMax > y;}
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int INF = 2147483647;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;

//???????????¢?´¢
struct Bfs
{
	set<string> memo;
	int search(string s)
	{
		queue<string> que;
		queue<int>    time;
		que.push(s);
		time.push(0);
		memo.insert(s);
		while(que.size())
		{
			string now = que.front();que.pop();
			int anstime = time.front();time.pop();
			//??????
			
			bool end = true;
			REP(i,now.size()-1)
			if(now[i] != now[i+1])
			end = false;
			if(end)return anstime; 
			//

			REP(i,now.size()-1)
			{
				string ts = now;
				char c0 = now[i];
				char c1 = now[i+1];
				char sc;
				if(c0 != c1)
				{
					if(c0 != 'b' && c1 != 'b')
						sc = 'b';
					if(c0 != 'r' && c1 != 'r')
						sc = 'r';
					if(c0 != 'g' && c1 != 'g')
						sc = 'g';
					
					ts[i] = sc;ts[i+1] = sc;
					if(!memo.count(ts))
					{
						memo.insert(ts);
						que.push(ts);
						time.push(1+anstime);
					}
				}
			}
		}
		return -1;
	}
};

int main()
{
	string str;
	while(cin >> str && str != "0")
	{
		Bfs bfs;
		int ans = bfs.search(str);
		if(ans == -1)
			cout << "NA" << endl;
		else
			cout <<  ans << endl;
	}
	return 0;
}


//????¬????????????????????????¨?????????
/*
	REP(i,mx)
	{
		REP(j,my)
		cout << n[i][j];
		cout << endl;
	}
	cout << endl;
*/