table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"}

until (worm = $<.gets.chomp) == "0"
  queue = [worm]
  dist = {worm => 0}
  n = worm.size
  catch :jump do
    while (worm = queue.shift)
      goal = ["r" * n, "g" * n, "b" * n]
      if goal.include?(worm)
        puts dist[worm]
        throw :jump
      else
        (n - 1).times do |i|
          tmp = worm.dup
          pair = worm[i, 2]
          next unless table[pair]
          tmp[i, 2] = table[pair]
          next if dist[tmp]
          dist[tmp] = dist[worm] + 1
          queue << tmp
        end
      end
    end
    puts "NA"
  end
end
