#include <iostream>
#include <queue>
#include <bitset>
using namespace std;

int main(){
	int n, g, b, c, x, y, i, c1, c2;
	char s[20];
	for(; cin >> s, *s - '0';){
		bitset<0xAAAAB> t;
		queue<int> q;
		for( x = n = 0; s[n]; n++ ){
			x |= ( s[n] == 'b' ? 2 : s[n] == 'g' ) << ( 2 * n );
		}
		n *= 2;
		g = 0x55555 & ( 1 << n ) - 1;
		b = 0xAAAAA & ( 1 << n ) - 1;

		q.push(x);
		q.push(-1);
		c = 0;
		for(; q.size() > 1; ){
			x = q.front();
			if( !x || x == g || x == b ){	break;	}
			q.pop();
			if( x == -1 ){	++c;	q.push(-1);	}
			else{
				c1 = x & 3;
				for( i = 2; i < n; i += 2 ){
					c2 = x >> i & 3;
					if( c1 != c2 ){
						y = x & ~( 15 << i - 2 );
						y |= ( 3 - c1 - c2 ) * 5 << i - 2;
						if( !t[y] ){
							t.set(y);
							q.push(y);
						}
					}
					c1 = c2;
				}
			}
		}
		if( q.size() > 1 ){	cout << c << "\n";	}
		else{	cout << "NA\n";	}
	}
}