A14766 | Reverse Sort

Ashish has a binary string $s$ of length $n$ 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 $k$ such that $1 \leq k \leq n$ and any sequence of $k$ indices $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ such that $s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$ .
2. Reverse this subsequence in-place. Formally, swap $s_{i_1}$ with $s_{i_k}$ , swap $s_{i_2}$ with $s_{i_{k-1}}$ , $\ldots$ and swap $s_{i_{\lfloor k/2 \rfloor}}$ with $s_{i_{\lceil k/2 \rceil + 1}}$ (Here $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$ , and $\lceil x \rceil$ denotes the smallest integer not less than $x$ )

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 $n$ operations.

The first line contains a single integer $t$ $(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 $n$ $(1 \le n \le 1000)$ — the length of the binary string $s$ .

The second line of each test case contains a binary string $s$ of length $n$ containing only $0$ s and $1$ s.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$ .

For each test case output the following:

- The minimum number of operations $m$ in the first line ( $0 \le m \le n$ ).
- Each of the following $m$ lines should be of the form: $k$ $i_1$ $i_2$ ... $i_{k}$ , where $k$ is the length and $i_1 \lt i_2 \lt ... \lt i_{k}$ are the indices of the chosen subsequence. For them the conditions from the statement must hold.