#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cstdio>
using namespace std;

typedef pair<string,bool> P;

int main()
{

  string worm;

  while(cin >> worm && worm != "0")
    {

      map<string,bool> state_record;
      queue<string> worm_state;
      bool NAflag = false;
      bool flag = false;
      int rank = 0;

      worm_state.push(worm);

      while(!flag && !NAflag)
        {

          string temp;
          int state_num = worm_state.size();
          int count = 0;

          NAflag = true;

          for(int j = 0; j < state_num && !flag;j++)
            {

              if(state_record[worm_state.front()] == true)
                {
                  worm_state.pop();
                  continue;
                }
              for(int i = 0; i < worm.length() - 1 && !flag; i++)
                {

                  temp = worm_state.front();

                  if(!temp.compare(i, 2, "rg") || !temp.compare( i, 2, "gr"))
                    {
                      temp.replace(i,2,"bb");
                      worm_state.push(temp);
                    }
                  else if(!temp.compare(i, 2, "rb") || !temp.compare(i, 2, "br"))
                    {
                      temp.replace(i,2,"gg");
                      worm_state.push(temp);
                    }
                  else if(!temp.compare(i, 2, "gb") || !temp.compare(i, 2, "bg"))
                    {
                      temp.replace(i,2,"rr");
                      worm_state.push(temp);
                    }

                  count = 0;

                  for(int t = 0; t < worm.length(); t++) if(temp[0]==temp[t]) count++;

                  if(count == worm.length()) flag = true;

                }

              state_record[worm_state.front()] = true;

              worm_state.pop();

              NAflag = false;

            }

          if(!worm_state.empty()) rank++;

          if(flag) cout << rank << endl;

          if(NAflag) cout << "NA" << endl;

        }

      state_record.clear();

    }

  return 0;

}