¡Ha comenzado la generación del mito!

Ina recibe una cadena $S$ de longitud $N$, formada únicamente por los caracteres I, C y P.

Su tarea consiste en extraer repetidamente la subcadena ICPC de $S$ tantas veces como sea posible. Cada vez que extrae ICPC, debe elegir cuatro caracteres de $S$ en orden (no necesariamente contiguos, pero respetando el orden original) que formen ICPC. Después de cada extracción, los caracteres elegidos se eliminan de la cadena. Los caracteres restantes cierran los huecos y forman la nueva cadena para la siguiente extracción.

Debes ayudarla a determinar el número máximo de veces que puede extraer ICPC y los índices (comenzando en 1) de los caracteres eliminados de la cadena original $S$ en cada extracción.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 1000$): el número de casos de prueba.

Cada caso de prueba contiene una sola línea con la cadena $S$, formada únicamente por los caracteres I, C y P.

Se garantiza que la suma de las longitudes de $S$ en todos los casos de prueba no supera $2 \cdot 10^5$.

Salida

Para cada caso de prueba:

Primero, imprime una línea con un entero $K$: el número máximo de extracciones de ICPC.

Después, imprime $K$ líneas, cada una con cuatro enteros: las posiciones de los caracteres eliminados durante esa extracción, con respecto a la cadena original.

Si hay muchas maneras de realizar las extracciones, imprime cualquiera de ellas.

Ejemplos

Entrada 1

4
PICPPC
ICPICPCCI
CIPCICICPPCCP
IPCC

Salida 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