G. Sequence Operation 1
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an integer sequence $$$a$$$ of length $$$n$$$ with values in $$$[0,2]$$$.

An operation is defined as choosing an index $$$x\in [1,n-2]$$$:

- Let $$$s=(a_x+a_{x+1}+a_{x+2})\bmod 3$$$, then set $$$a_x,a_{x+1},a_{x+2}$$$ all to $$$s$$$ simultaneously.

You need to perform some operations (possibly none) to maximize the sum of all elements in sequence $$$a$$$. Additionally, you must provide a valid operation sequence whose length does not exceed $$$\lfloor\dfrac{5}{7}n\rfloor+100$$$.

Input

This problem has multiple test cases.

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

For each test case:

The first line contains an integer $$$n$$$ — the length of sequence $$$a$$$.

The second line contains $$$n$$$ integers, where the $$$i$$$-th integer is $$$a_i$$$.

Output

For each test case:

The first line should contain two integers $$$s$$$ and $$$K$$$ — the maximum sum of the sequence and the number of operations, respectively. You must ensure $$$0\le K\le \lfloor\dfrac{5}{7}n\rfloor+100$$$.

The next line should contain $$$K$$$ positive integers, where the $$$i$$$-th integer is the index $$$x$$$ chosen in the $$$i$$$-th operation.

Example
Input
3
3
0 1 0
5
0 2 1 2 2
7
1 1 1 1 1 1 1
Output
3 1
1
10 4
2 2 3 1
14 5
1 3 4 5 1
Note

For $$$100\%$$$ of the data, it is guaranteed that $$$1\le T\le 1000$$$, $$$\sum n\le 10^6$$$, $$$3\le n\le 10^6$$$, $$$0\le a_i\le 2$$$.