Rozpoczęło się tworzenie mitu!

Ina otrzymuje napis $S$ długości $N$, składający się wyłącznie ze znaków I, C oraz P.

Jej zadaniem jest wielokrotne wyciąganie podnapisu ICPC z $S$, możliwie jak najwięcej razy. Za każdym razem, gdy wyciąga ICPC, musi wybrać z $S$ cztery znaki w kolejności (niekoniecznie sąsiadujące, ale z zachowaniem pierwotnej kolejności), które tworzą ICPC. Po każdym wyciągnięciu wybrane znaki są usuwane z napisu. Pozostałe znaki zamykają powstałe luki i tworzą nowy napis do następnego wyciągnięcia.

Musisz pomóc jej ustalić maksymalną liczbę wyciągnięć ICPC oraz indeksy (liczone od 1) znaków usuwanych z pierwotnego napisu $S$ przy każdym wyciągnięciu.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 1000$) — liczbę przypadków testowych.

Każdy przypadek testowy zawiera jeden wiersz z napisem $S$, składającym się wyłącznie ze znaków I, C oraz P.

Gwarantuje się, że suma długości $S$ we wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego:

Najpierw wypisz wiersz z liczbą całkowitą $K$ — maksymalną liczbą wyciągnięć ICPC.

Następnie wypisz $K$ wierszy, z których każdy zawiera cztery liczby całkowite — pozycje znaków usuniętych przy danym wyciągnięciu, względem pierwotnego napisu.

Jeżeli istnieje wiele sposobów wyciągania, wypisz dowolny z nich.

Przykład

Wejście 1

4
PICPPC
ICPICPCCI
CIPCICICPPCCP
IPCC

Wyjście 1

1
2 3 5 6
2
1 2 3 7
4 5 6 8
2
2 4 9 11
5 6 10 12
0