#P1572B. Xor of 3

    ID: 1837 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 9 Uploaded By: Tags>brute forceconstructive algorithmsgreedytwo pointers*2500

Xor of 3

Description

You are given a sequence aa of length nn consisting of 00s and 11s.

You can perform the following operation on this sequence:

  • Pick an index ii from 11 to n2n-2 (inclusive).
  • Change all of aia_{i}, ai+1a_{i+1}, ai+2a_{i+2} to aiai+1ai+2a_{i} \oplus a_{i+1} \oplus a_{i+2} simultaneously, where \oplus denotes the bitwise XOR operation
Find a sequence of at most nn operations that changes all elements of aa to 00s or report that it's impossible.

We can prove that if there exists a sequence of operations of any length that changes all elements of aa to 00s, then there is also such a sequence of length not greater than nn.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1041 \le t \le 10^4).

The first line of each test case contains a single integer nn (3n21053 \le n \le 2\cdot10^5) — the length of aa.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (ai=0a_i = 0 or ai=1a_i = 1) — elements of aa.

It is guaranteed that the sum of nn over all test cases does not exceed 21052\cdot10^5.

For each test case, do the following:

  • if there is no way of making all the elements of aa equal to 00 after performing the above operation some number of times, print "NO".
  • otherwise, in the first line print "YES", in the second line print kk (0kn0 \le k \le n) — the number of operations that you want to perform on aa, and in the third line print a sequence b1,b2,,bkb_1, b_2, \dots, b_k (1bin21 \le b_i \le n - 2) — the indices on which the operation should be applied.

If there are multiple solutions, you may print any.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1041 \le t \le 10^4).

The first line of each test case contains a single integer nn (3n21053 \le n \le 2\cdot10^5) — the length of aa.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (ai=0a_i = 0 or ai=1a_i = 1) — elements of aa.

It is guaranteed that the sum of nn over all test cases does not exceed 21052\cdot10^5.

Output

For each test case, do the following:

  • if there is no way of making all the elements of aa equal to 00 after performing the above operation some number of times, print "NO".
  • otherwise, in the first line print "YES", in the second line print kk (0kn0 \le k \le n) — the number of operations that you want to perform on aa, and in the third line print a sequence b1,b2,,bkb_1, b_2, \dots, b_k (1bin21 \le b_i \le n - 2) — the indices on which the operation should be applied.

If there are multiple solutions, you may print any.

Sample Input 1

3
3
0 0 0
5
1 1 1 1 0
4
1 0 0 1

Sample Output 1

YES
0
YES
2
3 1
NO

Note

In the first example, the sequence contains only 00s so we don't need to change anything.

In the second example, we can transform [1,1,1,1,0][1, 1, 1, 1, 0] to [1,1,0,0,0][1, 1, 0, 0, 0] and then to [0,0,0,0,0][0, 0, 0, 0, 0] by performing the operation on the third element of aa and then on the first element of aa.

In the third example, no matter whether we first perform the operation on the first or on the second element of aa we will get [1,1,1,1][1, 1, 1, 1], which cannot be transformed to [0,0,0,0][0, 0, 0, 0].