Background

This problem does not have any interesting background. Have fun.

Problem Description

Player A has a string $S$ made up only of A, P, and C.

Player A needs to eliminate as many as possible subsequences of the form APC from this string repeatedly, until no more eliminations can be done.

Finally, Player A needs to output the string after all eliminations. If the string can be eliminated into the empty string, output Perfect.

However, Player A cannot solve this problem, so they ask you for help.

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain a string $S$.

Output Format

This problem uses Special Judge.

Please output the shortest possible resulting string, and provide one deletion plan.

For each test case, output the following:

On the first line, output one shortest possible resulting string. If there are multiple shortest possible resulting strings or multiple plans to obtain a shortest resulting string, output any one of them.

On the next line, output an integer $q$, the number of deletions you perform.

On the next $q$ lines, output three integers each, representing the positions in the original string of the deleted characters A, P, and C in one operation. Indices start from $1$.

5
PAAAAPPPCA
CAPPCPCAPAPA
PPAAAACCAAAAAAAAC
CAPPCAAPA
APPAACPPAPPPAPAAAA

PAAAPPA
1
5 6 9
CPPCAPAPA
1
2 4 5
PPAAAACCAAAAAAAAC
0
CPAAPA
1
2 3 5
PAAPPAPPPAPAAAA
1
1 2 6

1
APC

Perfect
1
1 2 3

10
PPCPAPAAACPAPACPPCPC
APPAPPAPPCPAPPCCCPPA
APPCCPPAPPAACCPPPPPP
PACPPCAPCPPCPPPAAAAC
PPPCPPCCPACAAACCCCAC
ACAAPCPAPAAAAPPACPPC
ACACPPCCPPAACPAAAAAC
APPCPCCCAPCACPAACACC
AACPCAPACPPPCAAPCCPC
PPACPPPCCAPAAAPCPAPA

PPCPAAPP
4
5 6 10
7 11 15
8 13 18
9 16 20
PPPPPPPA
4
1 2 10
4 5 15
7 8 16
12 13 17
PCPPPAACPPPPPP
2
1 2 4
8 9 13
PCPPPCPPPAAAAC
2
2 4 6
7 8 9
PPPCPPCCPACAAACCCCAC
0
CAAAAAPPAPP
3
1 5 6
3 7 17
4 9 20
CCPPACAAAAA
3
1 5 7
3 6 8
11 14 20
PPCCCCAAACC
3
1 2 4
9 10 11
12 14 17
CP
6
1 4 5
2 7 9
6 10 13
8 11 17
14 16 18
15 19 20
PPCPPCAAAPPAPA
2
3 5 8
10 11 16

Hint

Sample Explanation #1:
For the first test case, the string is PAAAAPPPCA. Deleting the characters at indices $\{5,6,9\}$ results in PAAAPPA.

For the second test case, the string is CAPPCPCAPAPA. Eliminating the characters at indices $\{2,4,5\}$ results in CPPCAPAPA.

Sample Explanation #2:
In the only test case, the string is APC. Clearly, it can be completely eliminated, and the plan is also obvious.

$1\leq T\leq 10$, $1\leq \sum |S|\leq 3\times 10^6$.

Translated by ChatGPT 5