import qualified Data.Set as S
import Debug.Trace
main :: IO ()
main = do
  ls <- getLine
  if ls == "0"
    then return ()
    else do
      let ans = solve ls
      case ans of
        Nothing -> putStrLn "NA"
        Just n -> print n
      main

solve :: String -> Maybe Int
solve ls = func [ls] S.empty 0
  where
    func :: [String] -> S.Set String -> Int -> Maybe Int
    --func now visited count | traceShow (length now) False = undefined
    func now visited count
      | null now = Nothing
      | any f now = Just count
      | otherwise = func now' visited' (count + 1)
      where f :: String -> Bool
            f [] = True
            f (x:xs) = all (x ==) xs
            visited' = (foldr S.insert visited now)
            now' = filter (\x -> S.notMember x visited') (update now visited')
            update :: [String] -> S.Set String -> [String]
            update [] v = []
            update (x:xs) v = (filter (\x -> S.notMember x v) (g x)) ++ (update xs (foldr S.insert v (g x)))
              where
                g :: String -> [String]
                g (l:ls) = g' [l] ls []
                  where
                    g' :: String -> String -> [String] -> [String]
                    g' _ [] acc = acc
                    g' (x:xs) (y:ys) acc
                      | x == y = g' (y:x:xs) ys acc
                      | otherwise = g' (y:x:xs) ys (((reverse xs) ++ (newColor x y) ++ ys) `append` acc)
                      where
                        newColor c1 c2
                          |c1 /= 'b' && c2 /= 'b' = "bb"
                          |c1 /= 'r' && c2 /= 'r' = "rr"
                          |c1 /= 'g' && c2 /= 'g' = "gg"
                        append x xs = if (elem x xs) then xs else (x:xs)
                          