def bfs(bug)
  secs = {bug => 0}
  q = [bug]

  while b = q.shift
    return secs[b] if b.split(//).uniq.size == 1

    0.upto(b.size - 2) do |i|
      next if b[i] == b[i + 1]

      bt = b.dup
      bt[i, 2] = 'rgb'.delete(b[i, 2]) * 2
      next if secs[bt]

      secs[bt] = secs[b] + 1
      q.push bt
    end
  end

  'NA'
end

until (bug = gets.chomp) == '0'
  puts bfs(bug)
end