require "set"

def other_color(c, d)
  if c == d
    return c
  else
    diff = %w(r g b) - [c, d]
    return diff.first
  end
end

def next_worm(worm)
  pairs = worm.split('').each_cons(2).to_a
  others = pairs.map { |pr| other_color(*pr)}

  result = others.each_with_object([]).with_index{|(e, a), i|
    w = worm.dup
    w[i, 2] = e*2
    unless $found.include? w
      $found << w
      a << w
    end
  }
  result
end

def mono_color_time(init)
  $found = Set.new([init]) # 遷移して初期状態に戻る場合
  time = 0
  ws = [init]
  until ws.empty? or ws.any? { |w| w.split('').uniq.size == 1 }
    time += 1
    ws = ws.flat_map { |w| next_worm(w) }.uniq
  end
  ws.empty? ? 'NA' : time
end

loop do
  ln = gets.chomp
  break if ln == '0'
  puts mono_color_time(ln)
end
