In anticipation of a duel with his old friend Fernan, Edmond is preparing an energy drink called "Mishkin Energizer". The drink consists of a string $$$s$$$ of length $$$n$$$, made up only of the characters L, I, and T, which correspond to the content of three different substances in the drink.

We call the drink balanced if it contains an equal number of all substances. To boost his aura and ensure victory in the duel, Edmond must make the initial string balanced by applying the following operation:

Choose an index $$$i$$$ such that $$$s_i \neq s_{i+1}$$$ (where $$$i + 1$$$ must not exceed the current size of the string).
Insert a character $$$x$$$, either L, I, or T, between them such that $$$x \neq s_i$$$ and $$$x \neq s_{i+1}$$$.

Help Edmond make the drink balanced and win the duel by performing no more than $$$\textbf{2n}$$$ operations. If there are multiple solutions, any one of them can be output. If it is impossible, you must report this.

Input

Each test consists of several test cases. The first line of the input data contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the string $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting only of the characters L, I, and T.

Output

For each test case, output $$$-1$$$ if there is no solution. Otherwise, in the first line, output a single integer $$$m$$$ ($$$0 \le m \le 2n$$$) — the number of operations you performed.

Then the $$$l$$$-th of the following $$$m$$$ lines should contain a single integer $$$i$$$ ($$$1 \le i \lt n+l-1$$$), indicating the operation of inserting a character between $$$s_i$$$ and $$$s_{i+1}$$$. It must hold that $$$s_i \neq s_{i+1}$$$.

If there are multiple solutions, any one of them can be output. Note that you do not need to minimize the number of operations in this problem.

Note

In the first test case, the following sequence of operations can be performed: TILII $$$\rightarrow$$$ TLILII $$$\rightarrow$$$ TLTILII $$$\rightarrow$$$ TLTLILII $$$\rightarrow$$$ TLTLTILII.

In the second test case, no operations can be performed, so the answer is $$$-1$$$.

In the third test case, the initial string already has equal quantities of all substances.

Idx	Name	Rating
A	Kamilka and the Sheep	800
B	Lady Bug	1000
C	Asuna and the Mosquitoes	1200
D	Mishkin Energizer	1800
E	She knows...	2100
F	Andryusha and CCB	2900

Codeforces Round 1014 (Div. 2)