#P1605B. Reverse Sort

Reverse Sort

No submission language available for this problem.

Description

Ashish has a binary string ss of length nn that he wants to sort in non-decreasing order.

He can perform the following operation:

  1. Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any kk such that 1kn1 \leq k \leq n and any sequence of kk indices 1i1<i2<<ikn1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n such that si1si2siks_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}.
  2. Reverse this subsequence in-place. Formally, swap si1s_{i_1} with siks_{i_k}, swap si2s_{i_2} with sik1s_{i_{k-1}}, \ldots and swap sik/2s_{i_{\lfloor k/2 \rfloor}} with sik/2+1s_{i_{\lceil k/2 \rceil + 1}} (Here x\lfloor x \rfloor denotes the largest integer not exceeding xx, and x\lceil x \rceil denotes the smallest integer not less than xx)

Find the minimum number of operations required to sort the string in non-decreasing order. It can be proven that it is always possible to sort the given binary string in at most nn operations.

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

The first line of each test case contains an integer nn (1n1000)(1 \le n \le 1000)  — the length of the binary string ss.

The second line of each test case contains a binary string ss of length nn containing only 00s and 11s.

It is guaranteed that the sum of nn over all test cases does not exceed 10001000.

For each test case output the following:

  • The minimum number of operations mm in the first line (0mn0 \le m \le n).
  • Each of the following mm lines should be of the form: kk i1i_1 i2i_2 ... iki_{k}, where kk is the length and i1<i2<...<iki_1 \lt i_2 \lt ... \lt i_{k} are the indices of the chosen subsequence. For them the conditions from the statement must hold.

Input

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

The first line of each test case contains an integer nn (1n1000)(1 \le n \le 1000)  — the length of the binary string ss.

The second line of each test case contains a binary string ss of length nn containing only 00s and 11s.

It is guaranteed that the sum of nn over all test cases does not exceed 10001000.

Output

For each test case output the following:

  • The minimum number of operations mm in the first line (0mn0 \le m \le n).
  • Each of the following mm lines should be of the form: kk i1i_1 i2i_2 ... iki_{k}, where kk is the length and i1<i2<...<iki_1 \lt i_2 \lt ... \lt i_{k} are the indices of the chosen subsequence. For them the conditions from the statement must hold.

Samples

Sample Input 1

3
7
0011111
5
10100
6
001000

Sample Output 1

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

Note

In the first test case, the binary string is already sorted in non-decreasing order.

In the second test case, we can perform the following operation:

  • k=4:k = 4: choose the indices {1,3,4,5}\{1, 3, 4, 5\}

    1\underline{1} 00 1\underline{1} 0\underline{0} 0\underline{0} \rightarrow 0\underline{0} 00 0\underline{0} 1\underline{1} 1\underline{1}

In the third test case, we can perform the following operation:

  • k=3:k = 3: choose the indices {3,5,6}\{3, 5, 6\}

    00 00 1\underline{1} 00 0\underline{0} 0\underline{0} \rightarrow 00 00 0\underline{0} 00 0\underline{0} 1\underline{1}