Wstęp do programowania w C++

Na ile najwięcej fragmentów można podzielić ciąg liter tak, aby z każdego fragmentu (w którym można usuwać dowolnie litery) dało się uzyskać napis kot?

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się napis - ciąg małych liter alfabetu angielskiego o długości nieprzekraczającej 10⁶ znaków.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - największą liczbę fragmentów, na jakie można podzielić napis z wejścia. Jeśli taki podział nie jest możliwy, należy wypisać słowo NIE.

Przykład 1

Dla danych wejściowych:

kotzostajeresztaprosimyuciekacpredziutko

poprawną odpowiedzią jest:

1

Przykład 2

Dla danych wejściowych:

aktotoaktotoaktototakgna

poprawną odpowiedzią jest:

3

Przykład 3

Dla danych wejściowych:

jesliniccisieniechcetonapijsiewodybedziecisiechcialosiku

poprawną odpowiedzią jest:

NIE