#include <bits/stdc++.h>

using namespace std;

#define LOG(...) fprintf(stderr,__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(ALL(c))
#define RSORT(c) sort(RALL(c))

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;

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(len, 2, 11) {
        queue<vi> que;
        FOR(color, 1, 4) {
            vi v(10, 0);
            REP(i, len) v[i] = color;
            que.push(v);
        }
        que.push({});
        int cnt = 0;
        while (1) {
            vi v = que.front(); que.pop();
            if (v.empty()) {
                if (que.empty()) break;
                que.push({});
                cnt++;
                continue;
            }
            if (worm[v[9]][v[8]][v[7]][v[6]][v[5]][v[4]][v[3]][v[2]][v[1]][v[0]] != -1) continue;
            worm[v[9]][v[8]][v[7]][v[6]][v[5]][v[4]][v[3]][v[2]][v[1]][v[0]] = cnt;
            REP(i, len-1) {
                if (v[i+1] != 0 && v[i] == v[i+1]) {
                    int c1 = (v[i]) % 3 + 1, c2 = (v[i]+1) % 3 + 1;
                    vi v1 = v;
                    v1[i] = c1, v1[i+1] = c2;
                    que.push(v1);
                    vi v2 = v;
                    v2[i] = c2, v2[i+1] = c1;
                    que.push(v2);
                }
            }
        }
    }

    string line;
    while (cin >> line, line != "0") {
        vi v(10, 0);
        REP(i, line.size()) v[i] = line[i] % 3 + 1; // rgb -> 123
        int res = worm[v[9]][v[8]][v[7]][v[6]][v[5]][v[4]][v[3]][v[2]][v[1]][v[0]];
        if (res == -1) {
            cout << "NA" << endl;
        } else {
            cout << res << endl;
        }
    }
}