#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1};
int worm[4][4][4][4][4][4][4][4][4][4];

int main() {
	fill_n((int *)worm, 4*4*4*4*4*4*4*4*4*4, -1);

	FOR(n, 2, 10 + 1){
		queue<vi> que;
		REP(c, 3){
			vi w(10, 0);
			REP(i, n){
				w[i] = c+1;
			}
			worm[w[0]][w[1]][w[2]][w[3]][w[4]][w[5]][w[6]][w[7]][w[8]][w[9]] = 0;
			que.push(w);
		}
		que.push({});

		int step = 1;
		while(1){
			vi p = que.front(); que.pop();
			if(p.size() == 0){
				if(que.empty())
					break;
				step ++;
				que.push(p);
			}
			FOR(i, 1, p.size()){
				if(p[i-1] != p[i]) continue;
				if(p[i] == 0)continue;
				vi w1 = p;
				w1[i-1] = p[i-1] % 3 + 1;
				w1[i  ] = (p[i-1] + 1) % 3 + 1;
				vi w2 = p;
				w2[i-1] = (p[i-1] + 1) % 3 + 1;
				w2[i  ] = p[i-1]% 3 + 1;

				if (worm[w1[0]][w1[1]][w1[2]][w1[3]][w1[4]][w1[5]][w1[6]][w1[7]][w1[8]][w1[9]] == -1){
					worm[w1[0]][w1[1]][w1[2]][w1[3]][w1[4]][w1[5]][w1[6]][w1[7]][w1[8]][w1[9]] = step;
					que.push(w1);
				}
				if (worm[w2[0]][w2[1]][w2[2]][w2[3]][w2[4]][w2[5]][w2[6]][w2[7]][w2[8]][w2[9]] == -1){
					worm[w2[0]][w2[1]][w2[2]][w2[3]][w2[4]][w2[5]][w2[6]][w2[7]][w2[8]][w2[9]] = step;
					que.push(w2);
				}
			}
		}
	}

	string wm;
	while(cin >>wm, wm != "0"){
		vi w(10, 0);
		REP(i, wm.length()){
			w[i] = wm[i] % 3 + 1;
		}

		if(worm[w[0]][w[1]][w[2]][w[3]][w[4]][w[5]][w[6]][w[7]][w[8]][w[9]] == -1)
			cout << "NA" << endl;
		else
			cout << worm[w[0]][w[1]][w[2]][w[3]][w[4]][w[5]][w[6]][w[7]][w[8]][w[9]] << endl;
	}
}