colors = [?r, ?g, ?b]

loop do
	s = gets.chomp	
	break if s == ?0
	a = s.scan(/./)
	queue = [a]
	d = 0
	
	if a.uniq.size == 1
		puts 0
		next
	end

	reached = {a => 0}
	found = false
	loop do
		next_queue = []
		until queue.empty?
			a = queue.pop
			if a.uniq.size == 1
				next_queue = []
				found = true
				break
			end
			a.each_cons(2).with_index do |(x, y), i|
				if x != y
					c = a.dup
					z = (colors - [x, y])[0]
					c[i] = c[i+1] = z
					next if reached[c]
					reached[c] = 0
					next_queue << c
				end
			end
		end

		if next_queue.empty?
			puts found ? d : 'NA'
			break
		end
		d += 1
		queue = next_queue
	end
end