#include <cstdio>
#include <utility>
#include <queue>
#include <map>
using namespace std;

#define F(X,Y) ((X)>>((Y-1)*2)&3)

typedef pair<int,int> P;

int main() {
	char st[10];
	while(scanf("%s",st),st[0]!='0') {
		queue<P> que;
		map<int,bool> mp;
		int x=0,d;
		for(d=0;st[d]!='\0';d++) {
			x<<=2;
			x|=st[d]=='r'?0:st[d]=='b'?1:2;
		}
		mp[x]=true;
		que.push(P(x,0));
		int ans=-1;
		while(!que.empty()) {
			P p=que.front();
			que.pop();
			x=p.first;
			bool b=true;
			for(int i=d;i>1;i--) {
				int t1=F(x,i),t2=F(x,i-1),t3=3-(t1+t2);
				if(t1==t2) continue;
				else b=false;
				int y=0;
				for(int j=d;j>0;j--) {
					y<<=2;
					y|=(j==i||j==(i-1))?t3:F(x,j);
				}
				if(!mp[y]) {
					mp[y]=true;
					que.push(P(y,p.second+1));
				}
			}
			if(b) {ans=p.second; break;}
		}
		printf(ans==-1?"NA\n":"%d\n",ans);
	}
}