#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int d[1 << 22];
void p(int s, int n)
{
	for (int i = n-1; i >= 0; --i)
	{
		int t = (s & (3 << 2*i)) >> 2*i;
		if (t == 1)
			putchar('r');
		else if (t == 2)
			putchar('g');
		else if (t == 3)
			putchar('b');
		else
			putchar('*');
	}
}
int main()
{
	char buf[16];
	while (cin.getline(buf, sizeof(buf)), *buf != '0')
	{
		int n = strlen(buf);
		int initial = 0;
		for (int i = 0; i < n; ++i)
		{
			int t;
			if (buf[i] == 'r')
				t = 1;
			else if (buf[i] == 'g')
				t = 2;
			else
				t = 3;

			initial = (initial << 2) | t;
		}

		memset(d, -1, sizeof(d));
		d[initial] = 0;
		queue<int> state;
		state.push(initial);
		int ans = -1;
		while (!state.empty())
		{
			int s = state.front();
			state.pop();
			bool ok = true;
			for (int i = 0; i < n-1; ++i)
			{
				int r = (s & (3 << 2*i)) >> 2*i;
				int l = (s & (3 << 2*(i+1))) >> 2*(i+1);
				bool same = l == r;
				ok &= same;
				if (!same)
				{
					int color = -1;
					for (int j = 1; j <= 3; ++j)
						if (j != l && j != r)
							color = j;
					int next = s & ~(15 << 2*i) | (5*color << 2*i);
					if (d[next] == -1)
					{
						d[next] = d[s] + 1;
						state.push(next);
					}
				}
			}
			if (ok)
			{
				ans = d[s];
				break;
			}
		}
		if (ans != -1)
			printf("%d\n", ans);
		else
			puts("NA");
	}

	return 0;
}