I. ICPC Extractor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Myth generation has begun !

Ina is given a string $$$S$$$ of length $$$N$$$, consisting only of the characters 'I', 'C', and 'P'.

Her task is to repeatedly extract the substring "ICPC" from $$$S$$$ as many times as possible. Each time she extracts "ICPC", she must choose four characters from $$$S$$$ in order (not necessarily contiguous, but respecting the original order) that form "ICPC". After each extraction, the chosen characters are removed from the string. The remaining characters close the gap and form the new string for the next extraction.

You must help her determine the maximum number of times she can extract "ICPC" and the indices (1-indexed) of the characters removed from the original string $$$S$$$ for each extraction.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each testcase contains one single line of the string $$$S$$$, consisting only of the characters 'I', 'C', and 'P'.

It is guaranteed that the sum of the length of $$$S$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each testcase:

First, print a line with an integer $$$K$$$ — the maximum number of extractions of "ICPC".

Then print $$$K$$$ lines, each containing four integers — the positions of the characters removed during that extraction, based on the original string.

If there are many ways to extract, output any of them.

Example
Input
4
PICPPC
ICPICPCCI
CIPCICICPPCCP
IPCC
Output
1
2 3 5 6
2
1 2 3 7
4 5 6 8
2
2 4 9 11
5 6 10 12
0