#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e8
#define EPS 1e-9

#define rep2(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) rep2(i,0,n)
#define ll long long
#define P pair<int,int>
#define pb push_back

char c[]={'r','g','b'};
string s;

int main(){
	while(cin>>s&&s!="0"){
		map<string,int> M;
		queue<string> Q;
		M[s]=0;
		Q.push(s);
		int ans=INF;
		while(Q.size()){
			string s=Q.front();
			int step=M[s],same=0;
			Q.pop();
			rep(i,s.size()-1){
				if(s[i]!=s[i+1]){
					char a=s[i],b=s[i+1];
					rep(j,3){
						if(s[i]!=c[j]&&s[i+1]!=c[j]){
							s[i]=s[i+1]=c[j];
							break;
						}
					}
					if(!M[s]){
						M[s]=step+1;
						Q.push(s);
					}
					s[i]=a;s[i+1]=b;
				}
				else same++;
			}
			if(same==s.size()-1){
				ans=step;
				break;
			}
		}
		if(ans==INF)cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}
}