English statement

Dat vam je string ~S~ dužine ~N~. U jednom potezu možete da izaberete neki podniz stringa (ne obavezno uzastopnih slova), tako da slova podniza ~\textbf{redom}~ formiraju reč ~\textbf{algoge}~. Kada izvučete odabrani podniz dužine ~6~, u stringu vam ostane ~N-6~ slova u istom redosledu. Na novom stringu možete odigrati novi potez. Koliko najviše poteza možete odigrati?

Opis ulaza

• U prvoj liniji standardnog ulaza nalazi se ceo broj ~T~ (~1 \leq T \leq 10000~), broj odvojenih test primera.
• U svakoj od narednih ~T~ linija nalazi se po jedan string ~S~ za koji treba da odredite maksimalan broj poteza koji možete odigrati. Svaki od stringova sadrži samo mala slova engleskog alfabeta i suma dužina stringova u svim test primerima neće preći ~10^6~.

Opis izlaza

• U svakoj od ~T~ linija standardnog izalaza ispisati jedan broj, maksimalan broj poteza za taj test primer.

Primer ulaza

2
alalgogegogegogeal
nemozenamnikonistajacismoodsudbine

Primer izlaza

2
0

Objašnjenje primera

• U prvom test primeru moguće je izvući dva disjunktna podniza koji formiraju reč ~\textbf{algoge}~: ~(1, 2, 5, 6, 7, 8)~ i ~(3, 4, 9, 10, 11, 12)~.
• U drugom primeru ne možemo izvući podniz, string je baš onakav kakav treba da bude.