def make_somites(i, a)
    new_somites = a.dup
    if new_somites[i] != "r" && new_somites[i+1] != "r"
      new_somites[i] = "r"
      new_somites[i+1] = "r"
    elsif new_somites[i] != "b" && new_somites[i+1] != "b"
      new_somites[i] = "b"
      new_somites[i+1] = "b"
    else new_somites[i] != "g" && new_somites[i+1] != "g"
      new_somites[i] = "g"
      new_somites[i+1] = "g"
    end
    return new_somites
end

loop do
  insect = gets.chomp
  break if insect == "0"

  queue = []
  time = {count: 0}
  queue << [insect, time[:count]]
  len_insect = insect.length
  found = false

  # 過去に作られたwormであるかの判定、何度も出る場合は全てが同じ色になることはないのでNAを出力する
  reached = {a: true}

  loop do
    next_queue = []
    until queue.empty?
      target_somites = queue.shift
      if target_somites[0].split("").uniq.length == 1
        next_queue = []
        found = true
        break
      end

      (0..len_insect-2).each do |i|
        if target_somites[0][i] != target_somites[0][i+1]
          a = target_somites[0].dup
          new_somites = make_somites(i, a)
          next if reached[new_somites]
          reached[new_somites] = true
          next_queue << [new_somites, target_somites[1]+1]
        end
      end
    end
    
    if next_queue.empty?
      puts found ? target_somites[1] : "NA"
      break
    end
    queue = next_queue
  end
end

