import scala.io.Source.stdin
import scala.collection.mutable.Queue
import scala.collection.mutable.{ Set => mSet }

object Main {
  val rgb = "rgb".toCharArray

  def main(argv: Array[String]): Unit = {
    stdin.getLines.foreach { l =>
      if (l == "0") sys.exit()

      val q = new Queue[(String, Int)]()
      q.enqueue((l, 0))
      val rgbSet = mSet(Array.fill(l.length)("r").mkString,
        Array.fill(l.length)("g").mkString,
        Array.fill(l.length)("b").mkString)

      val done = mSet[String]()

      var continue = true

      if (rgbSet.contains(l)) {
        println(0)
        continue = false
      }
      while (continue && q.length > 0) {
        val (buf, time) = q.dequeue
        val pairs = (buf.drop(1) zip buf.take(buf.length-1)).map{ case (a, b) => Array(a, b) }.zipWithIndex

        pairs.foreach { case (arr, i) =>
          if (arr(0) != arr(1)) {
            val res = buf.take(i) + convert(arr).mkString + buf.drop(i + 2)
            // 終了判定
            if (rgbSet.contains(res)) {
              println(time+1)
              continue = false
            }
            if (!done.contains(res)) {
              q.enqueue(res -> (time+1))
              done += res
            }
          }
        }

        if (continue && q.length == 0) {
          println("NA")
        }
      }
    }
  }

  def convert(st: Array[Char]): Array[Char] = {
    val c = rgb.filterNot(c => st.contains(c))(0)
    Array(c, c)
  }
}

