Rak n Roll

Dzisiaj jest Twój wielki dzień, przeprowadzisz swoją pierwszą operację na oddziale onkologii. Dany jest ciąg komórek oznaczonych małymi literami alfabetu angielskiego. Musisz wybrać dowolne dwie spośród nich i zamienić je miejscami.

Odpowiedz na pytanie. Czy można zamienić miejscami dwie dowolne komórki, tak aby po wykonaniu zamiany ciąg nie zawierał podciągu spójnego rak?

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t ∈ [1, 100]. W kolejnych t liniach znajdują się zestawy danych.

Pojedynczy zestaw danych składa się z wyrazu określającego dany ciąg komórek. Wyraz złożony jest z małych liter alfabetu angielskiego, a jego długość zawiera się w przedziale [3, 10⁵].

Wyjście

Odpowiedź dla każdego zestawu danych należy wypisać w osobnej linii.

Jeżeli można zamienić miejscami dwie dowolne komórki, tak aby po wykonaniu zamiany ciąg nie zawierał podciągu spójnego rak, to wypisujemy słowo TAK oraz numery wybranych komórek. Komórki numerowane są od lewej strony do prawej począwszy od 1. Numery wybranych komórek muszą być różne. Jeżeli istnieje wiele rozwiązań wypisz dowolne z nich.

Jeżeli taka zamiana nie jest możliwa należy wypisać słowo NIE.

Przykład

Wejście:

3
pomagam
raknroll
niepomagamboniemamrakaaraktoproblemchorychnaraka

Wyjście:

TAK 1 2
TAK 1 3
NIE