#include <iostream>
#include <string>
#include <queue>
#include <set>

char change (char c1, char c2);
bool simple_check(std::string str); 
void bfs(std::string str); 


int main(void) {
    std::string str; 

    std::cin >> str;
    while (str != "0") {
        bfs(str); 
        std::cin >> str;
    }

    return 0;
}

char change (char c1, char c2) {
    char new_c;
    if (c1 != 'r' && c2 != 'r') {
        new_c = 'r'; 
    } else if (c1 != 'g' && c2 != 'g') {
        new_c = 'g'; 
    } else if (c1 != 'b' && c2 != 'b') {
        new_c = 'b'; 
    } else {
        std::cerr << "????????????" << std::endl;
    }
    return new_c;
}

bool simple_check(std::string str) {
    bool flag = true;
    for (int i = 0; i < str.size() - 1; i++) {
        if (str[i] != str[i + 1]) {
            flag = false;
        }
    }
    return flag;
}

void bfs(std::string str) {
    std::pair<std::string, int> now;
    std::queue<std::pair<std::string, int> > que; 
    std::set<std::string> st; 

    //use in while loop
    std::string str_cp;
    char remained_color;

    que.push(std::make_pair(str, 0));
    st.insert(str);


    while (! que.empty()) {
        now = que.front();
        que.pop();

        // ??¨?????????????????????break?????????
        if (simple_check(now.first) == true) {
            std::cout << now.second << std::endl; 
            return;
        }


        for (int i = 0; i < str.size() - 1; i++) {
            str_cp = now.first;
            if (str_cp[i] != str_cp[i + 1]) {
                remained_color = change(str_cp[i], str_cp[i + 1]);
                str_cp[i] = remained_color;
                str_cp[i + 1] = remained_color;
            }
            if (st.count(str_cp) == 0) {
                que.push(std::make_pair(str_cp,now.second + 1)); 
                st.insert(str_cp);
            }
        }
    }

    std::cout << "NA" << std::endl;
    return; 
}