#include<queue>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j,k;
  int n,p;
  bool b[3][3][3][3][3][3][3][3][3][3];
  string s;
  queue<pair<string,int> > c;
  while(cin>>s&&s[0]!='0'){
    n=s.length();
    for(i=0;i<10-n;i++)
      s+=(char)0;
    memset(b,0,59049);
    while(c.empty()==0)
      c.pop();
    c.push(make_pair(s,0));
    while(c.empty()==0){
      s=c.front().first;
      p=c.front().second;
      for(i=0;i<n;i++)
	s[i]+=3;
      j=0;
      for(i=0;i<n;i++){
	if(s[i]>2){
	  for(k=i+1;k<n;k++){
	    if(s[k]==s[i])
	      s[k]=j;
	  }
	  s[i]=j;
	  j++;
	}
      }
      for(i=1;i<n&&s[i-1]==s[i];i++);
      if(i==n)
	break;
      c.pop();
      bool* q=&b[(int)s[0]][(int)s[1]][(int)s[2]][(int)s[3]][(int)s[4]][(int)s[5]][(int)s[6]][(int)s[7]][(int)s[8]][(int)s[9]];
      if(*q==0){
	*q=1;
	for(i=1;i<n;i++){
	  if(0){
	  }else if(s[i-1]<s[i]){
	    if(0){
	    }else if(s[i]-s[i-1]==1){
	      s[i-1]=(s[i-1]+2)%3;
	      s[i]=(s[i]+1)%3;
	      c.push(make_pair(s,p+1));
	      s[i-1]=s[i-1]-2+(s[i-1]-2<0?3:0);
	      s[i]=s[i]-1+(s[i]-1<0?3:0);
	    }else if(s[i]-s[i-1]==2){
	      s[i-1]=(s[i-1]+1)%3;
	      s[i]=(s[i]+2)%3;
	      c.push(make_pair(s,p+1));
	      s[i-1]=s[i-1]-1+(s[i-1]-1<0?3:0);
	      s[i]=s[i]-2+(s[i]-2<0?3:0);
	    }
	  }else if(s[i-1]>s[i]){
	    if(0){
	    }else if(s[i-1]-s[i]==1){
	      s[i]=(s[i]+2)%3;
	      s[i-1]=(s[i-1]+1)%3;
	      c.push(make_pair(s,p+1));
	      s[i]=s[i]-2+(s[i]-2<0?3:0);
	      s[i-1]=s[i-1]-1+(s[i-1]-1<0?3:0);
	    }else if(s[i-1]-s[i]==2){
	      s[i]=(s[i]+1)%3;
	      s[i-1]=(s[i-1]+2)%3;
	      c.push(make_pair(s,p+1));
	      s[i]=s[i]-1+(s[i]-1<0?3:0);
	      s[i-1]=s[i-1]-2+(s[i-1]-2<0?3:0);
	    }
	  }	    
	}
      }
    }
    if(c.empty())
      cout<<"NA"<<endl;
    else
      cout<<p<<endl;
  }
  return 0;
}