#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;struct D{string s;int n;};main(){map<int,int>C;string s;int i,n,F;for(C[217]=98,C[201]='r',C[212]='g';cin>>s,s!="0";F?puts("NA"):printf("%d\n",n)){map<string,int>M;queue<D>q;D d={s,0};q.push(d);for(M[s]=1;q.size();){d=q.front();q.pop();s=d.s;n=d.n;for(i=F=0;++i<s.size();)if(s[i-1]-s[i]){D d={s,n+1};d.s[i-1]=d.s[i]=C[s[i-1]+s[i]];if(M.find(d.s)==M.end())q.push(d);F=M[d.s]=1;}if(!F)break;}}}