import scala.collection.mutable
object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val state = readLine.trim
    if (state == "0") return
    val color = state.map{
      case 'r' ⇒ 0
      case 'b' ⇒ 1
      case 'g' ⇒ 2
    }
    val minStep = Array.tabulate(exponent(3, state.length)){_ ⇒ -1}
    minStep(color.foldLeft(0){(a, b) ⇒ a * 3 + b}) = 0
    val queue = mutable.Queue[IndexedSeq[Int]]().also{q ⇒ q.enqueue(color)}
    while(queue.nonEmpty){
      val top = queue.dequeue()
      val topI = top.foldLeft(0){(a, b) ⇒ a * 3 + b}
      for (i ← state.indices.tail if top(i) != top(i - 1)) {
        val next = top.updated(i - 1, (top(i) + top(i - 1)) * 2 % 3).updated(i, (top(i) + top(i - 1)) * 2 % 3)
        val index = next.foldLeft(0){(a, b) ⇒ a * 3 + b}
        if (minStep(index) == -1){
          minStep(index) = minStep(topI) + 1
          queue.enqueue(next)
        }
      }
    }
    val green = minStep(exponent(3, state.length) - 1)
    val blue = minStep((exponent(3, state.length) - 1) / 2)
    val red = minStep(0)
    List(green, blue, red).filterNot(_ == -1) match {
      case Nil ⇒ println("NA")
      case l ⇒ println(l.min)
    }
    solve
  }
  def exponent(base: Int, exp: Int): Int = {
    exp match {
      case 0 ⇒ 1
      case 1 ⇒ base
      case _ ⇒ exponent(base, exp / 2).let{i ⇒ i * i * exponent(base, exp % 2)}
    }
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
  }
}
